编译原理学习笔记 4.3 递归下降子程序法

2023-07-20 22:19:40

前言

参考课上PPT内容。该学习笔记目前仅打算个人使用。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

跳过目录

一、递归下降子程序法（递归下降分析法）

具体做法：

对语法的每一个非终结符都编一个分析程序。
当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。
某个非终结符号的语法分析子程序的功能是，用该非终结符号的规则的右部符号串去匹配输入串。

例：文法G[E]：

E → UV
U → …
V → …

注：

消除左递归后，可有其它递归（如右递归或自嵌入递归）

U → …U 或 U → …U…
U → …W…
W → …U…

例：文法G[Z]

Z → ( U ) | aUb
U → dZ | Ud | e

1、检查并改写文法

Z → ( U ) | aUb
U → ( dZ | e ) { d }

注：Z → ( U ) 与 U → ( dZ | e ) 中括号意义并不一样，前者是终结符，后者是元语言符号。

改写后无左递归且首符集不相交：

{ ( } ∩ { a } = Ø
{ d } ∩ { e } = Ø

2、检查文法的递归性

Z ⇒ …U… ⇒ …Z…，∴ Z ⇒ + \stackrel{+}{\Rightarrow} ⇒+ …Z…
U ⇒ …Z… ⇒ …U…，∴ U ⇒ + \stackrel{+}{\Rightarrow} ⇒+ …U…

因此， Z和U的分析程序可以编成递归子程序

3、算法框图

说明：

非终结符号的分析子程序功能，是用规则右部符号串去匹配输入串。
要注意子程序之间的接口。在程序编制时，进入某个非终结符的分析程序前，其所要分析的语法成分的第一个符号已读入sym中了。
递归子程序法对应的是最左推导过程！
在上面的分析过程中，我们强调一定要消除左递归，但允许存在右递归或自嵌入递归。正是由于在子程序的调用过程中允许（直接或间接的）递归调用，这种方法才得名递归子程序法

例：文法：

改写文法：
<语句> → <变量> := <表达式> | IF <表达式> THEN <语句> [ ELSE <语句> ]
<变量> → i [ ‘[’<表达式>’]’ ]
<表达式> → <项> { + <项> }
<项> → <因子> { * <因子> }
<因子> → <变量> | ‘(’<表达式>’)’

语法分析程序所要调用的子程序：

getsym()：词法分析程序，每调用一次读进一个单词，单词的类别码放在sym中。
error()：出错处理程序。

void main() // 分析主程序
{
    getsym();    // 预读一个符号
    statement(); // 调用<语句>的分析子程序
}

void statement() // <语句>的分析子程序
{
    if (sym == "IF") // 判断是否是条件语句
    {
        getsym(); // 预读一个符号
        expr();   // 调用<表达式>分析子程序
        if (sym != "THEN")
            error();
        else
        {
            getsym();    // 预读一个符号
            statement(); // 调用<语句>的分析子程序
            if (sym == "ELSE")
            {
                getsym();    // 预读一个符号
                statement(); // 调用<语句>的分析子程序
            }
        }
    }
    else
    {
        var(); // 调用<变量>的分析子程序
        if (sym != ":=")
            error();
        else
        {
            getsym(); // 预读一个符号
            expr();   // 调用<表达式>的分析子程序
        }
    }
    printf("it is a statement.\n"); // 打印分析结论
}

void var() // <变量>的分析子程序
{
    if (sym != "i")
        error();
    else
    {
        getsym(); // 预读一个符号
        if (sym == "[")
        {
            getsym(); // 预读一个符号
            expr();   // 调用<表达式>的分析子程序
            if (sym != "]")
                error();
            else
                getsym(); // 预读一个符号
        }
    }
    printf("it is a variable\n"); // 打印分析结论
}

void expr() // <表达式>的分析子程序
{
    term(); // 调用<项>的分析子程序
    while (sym == "+")
    {
        getsym(); // 预读一个符号
        term();   // 调用<项>的分析子程序
    }
    printf("it is an expression\n"); // 打印分析结论
}

void term() // <项>的分析子程序
{
    factor(); // 调用<因子>的分析子程序
    while (sym == "*")
    {
        getsym(); // 预读一个符号
        factor(); // 调用<因子>的分析子程序
    }
    printf("it is a term\n"); // 打印分析结论
}

void factor() // <因子>的分析子程序
{
    if (sym == "(")
    {
        getsym(); // 预读一个符号
        expr();   // 凋用<表达式>的分析子程序
        if (sym != ")")
            error();
        else
            getsym(); // 预读一个符号
    }
    else
        var();                  // 调用<变量>的分析子程序
    printf("it is a factor\n"); // 打印分析结论
}

void error() // 出错处理程序
{
    printf("syntex error!\n"); // 报告错误
}

例：分析

if (i+i) then i:=i*i+i else i[i]:=i+i[i*i]*(i+i)

token ：
- if、then、else、(、+、)、:=、*、[、]、i

码农公寓

目录

一、递归下降子程序法（递归下降分析法）

相关文章