语法分析

发表于 2024-04-21 更新于 2024-05-05 阅读次数：本文字数： 354 阅读时长 ≈ 1 分钟

作用

输出语法分析树的某种形式

由终结符号、非终结符号、一个开始符号和一组产生式组成

上下文无关文法的表达能力比正则表达式强

最左推导：总是选择每个句型的最左非终结符号进行推导

最右推导：总是选择每个句型的最左非终结符号进行推导

每一棵语法分析树都和唯一的最左推导及唯一的最右推导相关联

如果一个文法中有一个非终结符A使得对某个串$\alpha$存在一个推导$A\Rightarrow A\alpha$，那么这个文法就是左递归的

自顶向下语法分析方法不能处理左递归的文法，所以要消除左递归

消除左递归

$FIRST(\alpha)$被定义为可从$\alpha$推导得到的串的首符号的集合

$FOLLOW(A)$被定义为可能在某些句型中紧跟在A右边的终结符号的集合

FIRST

FOLLW

LL1