【编译原理】第四章:语法分析
发布网友
发布时间：2023-02-23 02:20
共1个回答
热心网友
时间：2024-03-04 20:11
从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。
例：
总是选择每个句型的最左非终结符进行替换。
总是选择每个句型的最右非终结符进行替换。
在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为规范规约，对应的最右推导称为规范推导。
最左推导、最右推导具有唯一性。
自顶向下的语法分析采用最左推导方试，总是选择每个句型的最左非终结符进行替换。
由一组过程组成，每一个过程对应一个非终结符。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。
如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为回溯。
预测分析是递归下降分析技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法。
预测分析不需要回溯，具有确定性。
含有 形式产生式的文法称为是直接左递归的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是左递归的。其中，经过两步或以上推导产生的左递归，称为间接左递归的。
左递归会使递归下降分析器陷入无限循环。
文法
即
该文法是直接左递归的，会陷入无限循环。
将以上文法转换为：
即可消除左递归。事实上，这个过程把左递归转换成了右递归。
消除直接左递归的一般形式
使用代入法。
对于一个文法，通过改写产生式来推迟决定，等获得足够多的输入信息再做正确的决定。
例：文法：
可以改写为：
从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
S_文法（简单的确定型文法）
可能在某个举行中紧跟在A后面的终结符a的集合，记为FOLLOW(A)。
如果A是某个句型的最右符号，则将结束符“$”添加到FOLLOW(A)中。
例：文法：
中，FOLLOW(B) = {a, c}
产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A->β)。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)
q_文法
文法符号串α串首终结符的集合，记作FIRST(A)。
