龙书第二章 语法部分 - WinChua/blog GitHub Wiki

1. 语法定义

1.1 上下文无关法

• terminal(终止符号): 词法单元, 定义了该门语言的一些基本单元;
• non-terminal(非终止符号): 语法变量, 通过不断应用非终止符号的production rule, 可以最终得到一列关于终止符号的序列;
• production rules(生产式的集合): 每个生产式的左边部分包含一个非终结符号, 右边包含的是终止符号与非终止符号的序列;
• start symbol(开始符号): 指定某个非终止符号作为某个语言的开始符号.

1.2 上下文无关法的推导:

• 从start symbol开始, 通过不断替换其中的non-terminal, 最终我们会得到一系列的terminal;
• 文法定义的语言: 从start symbol开始可以通过推导得到的一些列terminal顺序的集合.

2. 语法分析:

• 任务: 给定一个终止符号序列的输入, 语法分析的任务就是:找出从文法的开始符号开始推导出当前terminal序列的方法;

2.1 语法分析方法的分类:

• 自顶向下
• 自底向上

2.2 自顶向下类方法:

• 自顶向下:

  • 构造某一个语法树的方法:
    • 从标号为A的non-terminal节点N上, 选择一个A的产生式, 将产生式中的各个标号作为N的子节点;
    • 从当前的节点中, 寻找下一个节点来构造子树;
  • 确定一个符号序列的语法树:
    • 给定一个terminal序列以及一个开始符号, 通过lookahead判断当前对应的production rule, 对语法树进行展开;
    • 重复上述步骤直到语法树中所有的叶子节点都是迭代完符号序列

• 递归下降法:

  • 在迭代符号序列的过程中, 每一个lookahead符号以及当前处于的父节点状态,唯一确定了当前应该使用的production规则;
  • 为了实现第一点, 我们需要直到每一个production rule对应的lookahead符号的集合, 通常记为FIRST(alpha);

2.3 文法中的左递归

** 只有当production rule中的一个终止符号被匹配成功了, lookahead才会改变 **

例如下面的文法:

expr -> expr + term

由于上面的production rule中, 左边部分与右边部分的最左节点是相同的, 而由于lookahead只有在输入token序列被成功匹配之后才会改变, 浙江会造成分析过程中无限循环

• 左递归的消除
  • expr -> expr + term | term : 这里的要求是term的FIRST set 不能够与expr的FIRST set 相同
  • expr -> term [ + R ]; R -> term [ + term ] : 这是右递归

3. 抽象语法树与语法分析树

3.1 区别:

语法树的内部节点表示的是程序内部结构; 语法分析树内部节点表示的是token中的non-terminal 符号。

文法中的很多非中介符号都代表了程序的构造，但也有部分的符号是一些辅助符号, 比如那些代表项目, 因子或者其他表达式变体。

有时候为了强调两者的区别, 会把语法分析树称为具体语法树, 而语法树称为抽象语法树.