编译原理第四章.ppt

1、第4章语法分析，语法分析程序的功能自上而下语法分析方法：迭代子程序方法，预测分析自下而上分析运算符优先级分析，l输入字符串和(莎士比亚、语法、语法、语法、语法、语法、语法、语法、语法) (寻找最左边的衍生之一)，分析过程实质上是考试过程。不确定的自上而下分析法实际上采用了所有可能的探索法。示例4.1 P58，S aAb A de | d，主要问题：(1)在无限循环语法中出现左递归时，分析过程陷入无限循环。(2)追溯存在同一未终止符号的多个候选项(例如，A 1|2|.|m派生过程中候选选择错误时，会发生回溯。(3)虚假匹配；(4)很难找到错误的位置。(5)效率低下。4.2.2语法的左递归和回溯剔

2、除，1，语法的左递归剔除，左递归：部分A的情况下，A=A有直接诱导左递归的剔除方法。引入新的非终结器A，将A替换为A A和A。示例4-2:表达式语法中的直接左递归删除E t e t e t e t f t * f t f (e) id，直接将左递归更改为右递归：规则A A1|A2|.|Am|1|2|.用：a1a | 2a |替换|n的注释：这不一定会删除整个语法的左递归。A Ac | Aad | BD | e，消除左递归法：(1)按一个顺序排列语法G的所有非终止符。(2)取代规则(例如for I :=1 to n do begin for j :=1 to I-1 do A B)的方法为B 1

3、| 2| k时，A 1| 2| k会直接从A规则中移除左侧递归；例如，移除间接左侧递归使用表达的出现是可选的。使用()从规则中提取系数。例如：et | e t f | t * f f I | (e)，使用扩展的backs-now范例表示：et t t t f * f f f f f f I |(e)，示例4.5 p60，a AC | aad唯一候选A 1.正确分配|m导致回溯原因：规则A b1|b2|.|m规则A i|和I，定义first，FOLLOW，SELECT集，非终止符A的后续规则选择集select (a)=，first ()=a | a，avt，FIRST如果生成了X，则添加FIRS

4、T(X)。3)如果有生成的X Y和Y N，则为FIRST(Y)的非元素FIRST(X)；已创建XY1Yk，对于I，为Y1.如果Yi-1=*，则FIRST(Yi)的所有非元素都将添加到FIRST(X)中。Y1.如果Yk=*，则添加到FIRST(X)中。，FIRST()计算方法？定义，例如表达式语法e t e t e t f t * f t f t f (e) id的FIRST集，first (f)=(，id first (t)=first (f)=()例如，# follow (e)=)、# follow (e)=follow (e)=)、# follow (t)=、# follow (t)，LL

5、(1)中：第一个L表示从左到右扫描输入字符串。第二个L表示在分析中使用最左边的导数1表示分析时，在每个步骤中只向前看一个符号，就可以确定选择的规则。这个选择是正确的。示例4.6 4.7 P61 - 62，定义，LL(1)语法条件：上下文无关语法G是LL(1)语法，只有G中的每个非终结器A的两个不同规则A|满足选择(A)时，才需要LL(1第二个L表示在分析中使用最左边的导数1表示分析时，在每个步骤中只向前看一个符号，就可以确定选择的规则。这个选择是正确的。示例4.6 P61 - 62，定义，示例4.7 p62，a ab | d b ba |，s aab a bb | da | b e | a，表

6、达式语法是LL(1)语法，e t e t e t e E:未终止的符号A 1|2|.|m面临的输入符号a 1)如果指定了aSELECT(A I)，则I 2)否则，A的出现是语法错误。即，有效的无回溯自上而下分析。例如，分析符号字符串id id * id与表达式语法匹配E t e t e t e t f t * f t f (e) id根据最左边的衍生进程来确定分析树、衍生进程、id、例如，具有左侧系数的语法stmt if expr stmt if expr stmtElse stmt other包含左侧系数if expr stmt、左侧系数提取方法、A 1 2.对于所有规则(例如n)，A A和

7、A12.n语法替代结果：stmt if expr stmt S other SElse stmt，示例4.8 P63，S ad | Ae A aS | bA，例如语法：saebd a aaeb abdb，note :并非所有郑智薰LL(1)语法都可以替换为LL(1)例如：为语言L=1na0n1ma0m|n0，m=0提供LL(1)语法GS，并说明GS是LL(1)语法的原因。4.2.4递归下降分析，递归下降分析程序的构造：为语法中的每个非终止符编写子程序，以标识非终止符表示的语法组件。这些子例程徐璐递归调用。，4.2.4递归下降分析，递归下降分析程序配置：各非终止子程序的配置：当存在多个此非终止子

8、规则时，可以根据LL(1)语法的条件唯一地选择候选规则(即程序的分支确定)。遇到结束符号A时：if(规则a: if(当前输入符号FOLLOW(A)error()，示例4.9 P65，递归子程序方法：1)语法编写，消除双重性2)去除左侧递归并提取左侧系数3，示例：表达式语法分析器，子程序/ET E()T()；/的调用while (sym=) /当前符号如下时的match()；/终止符t()；/的过程调用/sym:当前符号，的子程序T F*F，T()；f()；/的调用while (sym=*) /当前符号相同时的match(*)；/终止符f()；/的递归调用，的子程序F id|(E)，F()；If

9、 (sym=() /当前符号等于(match()。/处理终结器(e()；/的递归调用match()；/处理终止元)else if (sym=id) match(id) /处理终止元id else error() /错误处理，主程式，main () sym=/的调用if(sym=$)printf(“success！”)；else printf(“fail！”)；补丁程序(t:令牌)；if(sym=t)sym=next token；else error()；/错误处理程序、重复子程序方法的优缺点分析，优点：1)直观、简单、可读性好的2)扩展缺点：1)重复算法实现效率低的2)处理能力相对有限3)通用

10、性不足，难以自动生成，4.2.5预测分析程序方法矩阵元素表示在相应的生成或错误标志堆栈STACK中存储语法符号堆栈底部首先使用终结器$、预测分析器模型、a $、主程序、预测分析表M、输出、二维阵列非终结器A、终结器A表条目来表示生成或错误标志。X $一般结构和控制算法适用于特定于语言的处理分析表内容。不同的语言使用内容不同的分析表。优点：1)效率2)裴珉姬管理、自动创建、预测分析表配置算法：1，计算语法中每个非终结器的FIRST集和FOLLOW集，每个规则的SELECT集。2，1)每个生成A的2) 2)为选择(A)的每个终止符A(或$)填充A，并将A 3)所有未定义的MA、b标记为错误标记。，范例4.10 P67-68，范例表示式语法的LL(1)预测分析表格，执行范例：分析id*id、 堆栈输入缓冲区使用的结果$ e id * id $ $ et id * id $ e te $ ETF id id * id $ t ft $ etid id id * id $ f id $ et id * id $ et id $ id (语法替换)3)