网站建设中所需条件,有创意的文创产品,广州地铁21号线,东莞常平镇最好的工厂自底向上分析之算符优先分析法 说明#xff1a;以老师PPT为标准#xff0c;借鉴部分教材内容#xff0c;AlvinZH学习笔记。 基本过程 1. 一般方法#xff1a;采用自左向右地扫描和分析输入串#xff0c;从输入符号串开始#xff0c;通过反复查找当前句型的句柄#xff0…自底向上分析之算符优先分析法 说明以老师PPT为标准借鉴部分教材内容AlvinZH学习笔记。 基本过程 1. 一般方法采用自左向右地扫描和分析输入串从输入符号串开始通过反复查找当前句型的句柄最左简单短语并利用有关规则进行规约。 分析过程如下关键步骤是第一点 找出当前句型的句柄 x 或句柄的变形找出以 x 为右部的规则 X:: x 把 x 规约为X产生语法树的一枝。2. 自底向上分析也叫作移进-规约分析简单的例子中识别句柄的过程主要看栈顶符号串是否形成规则的右部。这种做法形式上正确但实际上不一定正确。原因不能认为对于句型xuy若有U::u就断定u是简单短语或者u是句柄也就是说这是一个必要不充分条件。 算符优先分析OPP 1. OPP简单直观广为使用的自底向上分析方法易手工实现。可用于一大类上下文无关文法。 分析器的结构符号栈、优先关系矩阵、分析程序。 2. 特点预先规定相邻终结符之间的优先关系利用优先关系确定句型的“句柄”并进行规约。 注意 这里的“句柄”有可能不是真正的句柄这种规约也未必是严格的最左规约。后续解释对于二义性文法如 \(E :: EE | E-E | E*E | E/E | (E) | i\)可以通过定义优先关系和左结合原则OPP可分析之。3. 终结符之间优先关系定义 a ba的优先级等于ba ba的优先级小于ba ba的优先级大于b注意 这个关系是单方面的也就是说这里的 “ab” 并不意味着 “ba”同样的“ab” 也不意味着 “ba”。 4. 优先关系举矩阵左终结符栈内、右终结符栈外值为优先关系空表示两个终结符不能相邻。 使用方法当栈顶项或次栈顶项 终结符的优先级大于栈外的终结符的优先级则进行规约否则移进。 出错情况 相邻终结符之间无优先关系。对双目运算符进行规约时符号栈中无足够项。非正常结束状态。5. 优先函数文法终结符之间的优先关系可以不用矩阵表示而是采用两个邮箱函数来表示f(x)表示栈内优先函数g(x)表示栈外优先函数。把优先关系的比较转换成数值的比较。 特点优先函数值不唯一只要相互之间数值大小表示优先关系就行。 优点节省内存空间易于比较数值比较 缺点可能掩盖错误由于优先关系变为数值原先可能不存在的优先关系现在也可比较了。可以通过特判避免这个问题。 OG与OPG定义 1. 算符文法OG若文法G中没有形如 \(U :: ···VW···\) 的规则V,W∈Vn则称G为算符文法。 直观理解算符文法不允许两个非终结符相邻 2. 优先关系定义设嗡文法G是一个OG文法a,b∈VtU,V,W∈Vn。 a b iff 文法中有形如 \(U∷…ab…\) 或 \(U∷…aVb…\) 的规则。a b iff 文法中有形如 \(U∷…aW…\) 的规则其中 \(W b…\) 或 \(W Vb…\)。a b iff 文法中有形如 \(U∷…Wb…\) 的规则其中 \(W …a\) 或 \(W …aV\)。TIP只是定义第二第三条实际用起来真的难用还是继续看下去用FIRSTVT和LASTVT高级操作吧 3. 算符优先文法OPG设有一OG文法如果在任意两个终结符之间至多只有上述关系中的一种则称该文法为算符优先文法OPG。 构造优先关系矩阵 1. 通过检查每一条规则 优先关系很容易求得但是 和 就复杂了需要引入两个集合辅助FIRSTVT、LASTVT。 FIRSTVT( U ) { b | U b…或U Vb…, b∈Vt , V∈Vn} LASTVT( U ) { a | U …a 或U …aV, a∈Vt , V∈Vn} 若文法有规则形如 \(W∷ ...a U...\)对任何 b∈FIRSTVT( U )则有 a b。 若文法有规则形如 \(W∷ ...U b...\)对任何 a∈LASTVT( U )则有 a b。 2.构造FIRSTVT集合 若有规则 U∷ b… 或 U∷ V b…则 b∈FIRSTVT(U)若有规则 U∷ V… 且 b∈FIRSTVT(V), 则 b∈FIRSTVT(U)。3.构造LASTVT集合 若有规则 U::…a 或 U::…aV则 a∈LASTVT(U)若有规则 U::…V且 a∈LASTVT(V) 则 a∈LASTVT(U)。4.构造算符优先矩阵 FOR 每条规则U:: x1 x2…xn DOFOR i:1 TO n-1 DOBEGINIF xi和xi1均为终结符, THEN 置 xixi1IF i≤n-2且xi和xi2都为终结符号但xi1为非终结符号 THEN 置 xixi2IF xi为终结符号xi1为非终结符号 THENFOR FIRSTVT(xi1)中的每个b DO 置xibIF xi为非终结符号xi1为终结符号 THENFOR LASTVT(xi)中的每个a DO 置axi1END 5. 举个例子 分析句子 \(i*(ii)\)。 分析算符优先分析法 1. 提出问题这种分析算法并不是严格的最左规约也就是说每次规约的未必是当前句型的句柄。那它规约的是什么 答案最左素短语。 先给出分析过程的特点不予证明 每次规约的最左子串确实是当前句型的最左素短语规约的不都是真正的句柄有时候是只是偶然没有完全按规则进行规约因为素短语不一定是简单短语有时候是只是偶然2. 素短语句型的素短语是一个短语它至少包含有一个终结符号并且除它自身以外不再包含其它素短语。 例如对于句型TTFi通过语法树可以轻易找到所有短语① T T F i② T T * F③ T④ T * F⑤ i。①包含其它短语②包含其它短语③不包含终结符④是素短语⑤是素短语。最后最左素短语就是④T*F。然而该句型的句柄确实③T。 3. 形式化寻找最左素短语设有OPG文法句型#N1 a1 N2 a2…Nn an Nn1 #其中Ni为非终结符可以为空ai为终结符。 定理一个OPG句型的最左素短语是满足下列条件的最左子串Nj aj … Ni ai Ni1其中aj-1 aj aj a . . . . j1 , aj1 aj2 , … , ai-2 ai-1 , ai-1 ai ai. ai1。 4. 实现算符优先分析法找句型的最左子串最左素短语并进行规约。 具体实现当栈内终结符的优先级或栈外终结符的优先级时移进当栈内终结符的优先级栈外终结符的优先级时表明找到了素短语的尾再往前找其头并进行规约。 引用说明 - 邵老师课堂PDF
- 《编译原理级编译程序构造》 转载于:https://www.cnblogs.com/AlvinZH/p/8309259.html
