编译原理 syntax analysis

语法分析

词法分析之后，拿到一系列token，然后经过了语法分析生成抽象语法树，如下所示： 其中的E类似一个占位符，在grammar中通过递归定义

按照步骤构造一个parser的过程如下：

3.1 Context-Free Grammars

在之前，我们的词义分析做到的是讲将所有的输入转化为了token序列，利用的工具是正则表达式；但是在检查语法的时候，就需要使用上下文无关语言检查语法（比方说，我要检查括号匹配（两边括号数量相同），就超出了FA的表达范围）

def left-most derivation（最左推导）：每次展开一个最左边的非终结符；类似地还有最右推导。如果一个文法没有歧义，二者推出的应当是同一个parse tree

3.2 Top-Down Parsing

我们主要关心无歧义文法的一个子集，即LL(1)文法；这是一种预测性的分析