编译原理ppt3_2
3.2 语言和文法,文法为语言给出了精确的、易于理解的语法说明 对于某些文法类，可以自动产生高效的分析器 如果文法设计得恰当，则它赋予语言的结构对于源程序翻译成正确的目标代码和对于错误诊断都是有用的 语言也是逐步完善的，增加新构造以完成新任务的情况时有发生。如果存在以文法为基础的语言的实现，语言新构造的加入就显得方便,文法能够描述程序设计语言的大部分语法成分，但不能描述程序设计语言的全部语法成分,3.2.1正规式和上下文无关文法的比较,正规表达式所描述的每一种结构都可以用上下文无关文法来描述 例如描述正规表达式(a|b)*abb的上下文无关文法A0 aA0 | bA0 | aA1A1 bA2A2 ,NFA -上下文无关文法 对NFA的每个状态i，创建一个非终结符Ai 如果状态i遇到输入符号a转换到状态j，则引入产生式Ai aAj 如果状态i遇到输入符号转换到状态j，则引入产生式Ai Aj 如果状态i是接受状态，则引入产生式Ai 如果状态i是开始状态，则Ai是文法的开始符号,对任何a及A,BS，若有(A,a)=B，则：(a) 当BF时，令AaB，(b) 当BF时，令Aa|aB。,例：设DFA M = 。M的状态转换图如下图所示，求等价的上下文无关文法,G=，其中P由下列产生式组成：A0B|1DB0D| 1C| C0B| 1DD0D|1D,A0| 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D,3.2.2 分离词法分析器的理由,为什么用正规式定义语言的词法，而不用上下文无关文法 语言的词法规则简单 正规式给出的描述更简洁且易于理解 从正规式自动构造出的词法分析器更有效,3.2.3验证文法产生的语言,文法G产生语言L：由G产生的每个字符串都在L中；反之，L中的每个字符串都能由G产生 例，下面的文法G能而且仅能产生所有配对的括号串S(S)S | ,文法示例,例1：G1S: S bAA aA | aL(G1)= ban | n1例2：G2S: S aSb | abL(G2)= anbn | n1,例3：构造文法G3，使L(G3)= anbn+1 | n0G3S: S aSb | b例4：构造文法G4，使L(G4)=| 为字符集上的回文，=a,bG4S: S aSa | bSb | a | b |,3.2.4 适当的表达式文法,通过改写文法来消除文法的二义性 例：Gexpr: exprexpr+expr | expr*expr | (expr) | id 可以改写为如下无二义文法 expr expr+term | term term term*factor | factor factor (expr) | id,将相同优先权的算符放在一组，并为每一种优先权规定不同的规则E E+E | TT T*T | FF (E) | i 文法中仍为指定算符的结合性，还具有二义性，用基本情况代替递归，强制重复算符匹配一边的递归,将规则 EE+E | T 替换为 EE+T | T (左结合)ET+E | T (右结合) 最后得到:G'EEE+T | TTT*F | FF (E) | i,3.2.5 消除二义性,例 stmt if expr then stmt| if expr then stmt else stmt| other 考虑：if E1 then if E2 then S1 else S2,每个else 和前面最近的没有配对的then配对,基本思想：出现在then和else之间的语句必须是“配对”的，即它不能以一个未配对的then后面跟随任意的非else语句结束，于是else会被迫与这个未配对的then匹配。,改写后的文法 stmt matched_stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt| if expr then matched_stmt else un matched_stmt,3.2.6 消除左递归,一个文法是含有左递归的，如果存在非终结符A，存在推导 消除直接左递归 将规则 AA | （其中不以A开头）改写为：AA'AA|,例：文法EE+T|TTT*F|FF(E)|id 消除左递归ETE'E'+TE'|TFT'T'*FT'| F(E)|id,一般形式的直接左递归AA1|A2|.|Am|1| 2|.| n消除A的左递归A 1A'| 2A'|.| nA'A' 1 A'| 2 A'|.|m A'| ,例如文法GSS Aa |bA Ac | Sd | 虽没有直接左递归，但S、A都是左递归的SAaSda,消除左递归的算法,(1)把文法G的所有非终结符按任一顺序排列成A1,A2,.An；按此顺序执行 (2)FOR i:=1 TO n DOBEGINFOR j:=1 TO i-1 DO把形如Ai Aj的规则改写成Ai 1| 2|.| k，其中 Aj1|2|.|k是关于Aj的所有规则消除关于Ai规则的直接左递归性END (3)化简由2得到的文法即可,间接左递归,直接左递归,消除 直接左递归,例如文法GSS Aa |bA Ac | Sd | 排序 S、A i=1，S没有直接左递归 i=2，对于A Ac | Sd | ，将关于S的产生式代入，得到A Ac | Aad | bd | ，消除A的左递归A bdA' | A'A' cA' | adA' |,最终得到消除了左递归后的文法S Aa |bA bdA' | A'A' cA' | adA' |,注意： 若非终结符排列顺序不同，改写后的文法也不同，但它们是等价的。 开始符号不能改变。,练习：消去文法G(S)的左递归 SQc|c QRb|b RSa|a,对非终结符排序：R、Q、S i=1, RSa|a没有直接左递归 i=2, 对于QRb|b将关于R的产生式替换Q产生式中的R，得到QSab|ab|b，Q中也没有直接左递归 i=3， 对于SQc|c将关于Q的产生式替换S产生式中的Q，得到SSabc|abc|bc|c，有直接左递归，消除后得到SabcS' | bcS' | cS'S'abcS' | QSab|ab|bRSa|a,由于R,Q对开始符号S来说都是不可达非终结符，所以删除它们。 故最后消除左递归后文法为GS：SabcS' | bcS' | cS'S' abcS| ,3.2.7 提左因子,基本思想：当不清楚应该用两个选择中的哪一个来替换非终结符A时，可改写A产生式来推迟这种决定，知道看到足够多的输入能做出正确选择为止。 例如 A 1|2，输入字符串由从导出的非空串开始，将此产生式改为AA'A'1|2,提取公共左因子将某产生式A1| 2|. | n| 1 |2 |. |m改写为 AA'| 1 |2 |. |mA'1|2|. |n 注： 通过反复提取左因子，就能把所有非终结符的所有候选首符集变为两两不相交。 反复提取左因子也有一定代价，因为在提取过程中会大量引入非终结符和产生式，增加语法分析的复杂性。,例：对下面的文法提取左因子 SiEtS | iEtSeS | a Eb 改写后的文法： SiEtSS' | a S'eS | Eb,例1：GSSxAyA*|*例2：GSSABc | ABd | AeAaf | agBb,SxAy A*A' A'* | ,SAS' S'Bc | Bd | e AaA' A'f | g Bb,SAS' S'BS“ | e S“c | d AaA' A'f | g Bb,3.2.9 形式语言鸟瞰,乔姆斯基把文法分成四种类型，即0型、l型、2型和3型。 描述能力：0型强于1型，l型强于2型，2型强于3型。,0型,1型,2型,3型,0型(短语文法，图灵机)：产生式形如： 其中： (VT VN)*且至少含有一个非终结符； (VT VN)* 1型(上下文有关文法，线性界限自动机)：产生式形如： 其中：| |，仅 S 例外。,2型(上下文无关文法，非确定下推自动机)：产生式形如： A 其中：A VN； (VT VN)*。3型(正规文法，有限自动机)：产生式形如： A B 或 A 其中： VT*；A，BVN （右线形文法）或者产生式形如： A B 或 A 其中： VT*；A，BVN （左线形文法）,
