编译原理习题课答案市公开课金奖市赛课一等奖课件

chapter11、何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？源程序：用源语言编写程序。目标程序：源程序经翻译程序过加工处理后生成程序。翻译程序：将源程序转换为与其逻辑上等价目标程序。编译程序：源语言为高级语言，目口号言为汇编语言或机器语言翻译程序。解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。①先翻译后执行①边解释边执行②执行速度快②

有利于程序调试③屡次运算③1次运算第1页2、一个经典编译系统通常由有哪些部分组成？各部分主要功效是什么？chapter1编译系统编译程序语法分析语义分析与中间代码生成优化目标代码生成运行系统词法分析第2页②语法分析(SyntaxAnalysis)：

在词法分析基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表示式”等等。③语义分析(SyntacticAnalysis)：

语义分析是在语法分析程序确定出语法短语后，审查有没有语义错误，并为代码生成阶段搜集类型信息。chapter1①词法分析(LexicalAnalysis)：

从左到右一个字符一个字符读入源程序，对组成源程序字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。

第3页chapter1⑤代码优化(Optimizationofcode)：

为了使生成目标代码更为高效，能够对产生中间代码进行变换或进行改造，这就是代码优化。⑥代码生成(Generationofcode)：

目标代码生成是编译器最终一个阶段。在生成目标代码时要考虑以下几个问题：计算机系统结构、指令系统、存放器分配以及内存组织等。④中间代码生成(Generationofintermediatecode)：

完成语法分析和语义处理工作后，编译程序将源程序变成一个内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一个结构简单、含义明确记号系统。第4页chapter21.写出C语言和Java语言输入字母表。C语言：0~9数字，大小写英文字母，键盘上可见字符Java语言：Unicode能够包含全部字符。6.文法G6为:N→D|NDD→0|1|2|3|4|5|6|7|8|9

（1）G6语言是什么?G6语言是：

0~9数字组成任意非空串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（2）给出句子0127、34和568最左和最右推导。第5页7、写一文法，使其语言是奇数集。要求：不以0打头。复杂情况:分三部分末尾：以1|3|5|7|9结尾(一位):D→1|3|5|7|9开头：除了0任意数字中间部分：空或者任意数字串D→1|3|5|7|9C→CA|εA→0|B所以题目要求文法G[N]能够写成：N→BCD|DD→1|3|5|7|9B→2|4|6|8|DC→CA|εA→0|BB→2|4|6|8|D第6页9、证实文法:S→iSeS|iS|i

是二义。二义性含义:假如文法存在某个句子对应两棵以上不一样语法树，或者两种以上不一样最左/右推导，则称这个文法是二义。首先：找到此文法对应一个句子iiiei其次：结构与之对应两棵语法树SiSeSiSiiSiSiSeSii结论：因为该文法存在句子iiiei对应两棵不一样语法树，因而该文法是二义。第7页11、给出下面语言对应文法L1={anbnci|n≥1,i≥0}G1(S):S→ABA→aAb|abB→cB|ε从n，i不一样取值来把L1分成两部分：A→aAb|ab前半部分是anbn：

后半部分是ci：B→Bc|ε所以整个文法G1[S]能够写为：第8页L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|ε第9页L4={1n0m1m0n|n,m≥0}能够看成是两部分：剩下两边部分就是：S→1S0中间部分是0m1m

：A→0A1|ε所以G4[S]能够写为：S→1S0|AA→0A1|ε|A第10页chapter37.结构以下正规式对应DFA。步骤:①.依据正规式画出对应状态转换图;②.依据状态转换图画出对应状态转换矩阵;③.依据状态转换矩阵得到重命名后状态转换矩阵;④.依据重命名后状态转换矩阵得出最终DFA.问题：将状态转换图与DFA混同。第11页1(0|1)*101①.状态转换图abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg第12页②.状态转换矩阵II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101g第13页II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后状态转换矩阵S01A(始态)ΦBBCDCCDDEDECF(终态)F(终态)EDAB10C1D010E10101F④.DFA第14页1(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.状态转换图第15页②.状态转换矩阵II

0I

1{0}Φ{1,2,3}{1,2,3}{4}{5,9,10,11}{5,9,10,11}{6,12}{2,3}{6,12}Φ{2,3,7,8,13}{2,3}{4}{5,9,10,11}{2,3,7,8,13}{2,3,4,8,10,11}{5,9,10,11}{2,3,4,8,10,11}{2,3,4,8,12}{2,3,5,9,10,11}{2,3,4,8,12}{2,3,4,8}{5,9,10,11,13}{2,3,5,9,10,11}{4,6,12}{2,3,5,9,10,11}{2,3,4,8}{2,3,4,8}{5,9,10,11}{5,9,10,11,13}{6,10,11,12}{2,3}{4,6,12}Φ{2,3,7,8,13}{6,10,11,12}{12}{2,3,7,8,13}{12}Φ{13}{13}{10,11}Φ{10,11}{12}{2,3}第16页③.重命名后状态转换矩阵II

0I

11Φ22344565Φ7634784891091112101310111141214613Φ71415715Φ161617Φ17156④.DFA第17页8、给出下面正规表示式（1）以01结尾二进制数串。(0|1)*01（2）能被5整除十进制数。0|5(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*（4）英文字母组成全部符号串，要求符号串中字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（3）包含奇數個1或奇數個0二進制串0*1(0|10*1)*|1*0(0|10*1)*第18页（5）沒有重複出現數字數字符號串全體令ri=i|,i=0,1,2...9R0|R1|R2|...|R9記為∑Rii(0,1,2...,9)P（0,1,2...,9)表示0,1,2...,9全排列∑ri0ri1...ri9ri0ri1...ri9

P(0,1,2...,9)8、给出下面正规表示式（6）最多有一個重複出現數字數字符號串全體∑i∑ri0ri1...ri9

i(0,1,2...,9)ri0ri1...ri9P(0,1,2...,9)（7）不包含字串abb由a和b組成符號串全體b*(a*|(ba)*)*第19页9、对下面情况给出DFA及正规表示式：（1）{0,1}上含有子串010全部串。正规式：(0|1)*010(0|1)*DFA做法同第7题。（2）{0,1}上不含子串010全部串。正规式：1*(0|11*1)*1*0*1*(0|11)*(0|1)1*(0|11)*1*第20页12、将图3.18(a)和(b)分别确定化和最少化。(a)aaa,b10①.状态转换矩阵IIaIb

{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后状态转换矩阵IIaIb

01221120φ0a2baba③.DFA④.最小化Π0=({0,1},{2})1{0,1}a={1}{0,1}b={2}所以，不能再分02baa第21页023145aaaabbbbbbaa(b)这道题实质上已经是确定化了，所以我们只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}a={0，1，3，5}分属两区，所以分为{2，4}{3，5}{0，1}a={1}{0，1}b={2，4}所以0，1等价{2，4}a={0，1}{2，4}b={3，5}所以2，4等价{3，5}a={3，5}{3，5}b={2，4}所以3，5等价所以分为

{0，1}{2，4}{3，5}

023aabbba第22页14、结构一个DFA，它接收Σ={0,1}上全部满足以下

条件字符串：每个1都有0直接跟在右边。思绪：先写出满足条件正规式，由正规式结构

NFA，再把NFA确定化和最小化。满足条件正规式：(0|10)*0110yx(0|10)*xy12100第23页xy12100确定化：01{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φ给状态编号：0101211221φ第24页021

01100最小化：{0,1}，{2}{0,1}0={1}{0,1}1={2}{2}0={0}，{2}1=

∅⊆{2}或{0,1}所以{0,1}不可分，用狀態0代表它們02100第25页15、给定右线性文法G：求一个与G等价左线性文法。S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1SABCZ001110001101G[Z]:Z→Z0|Z1|B0|A1B→A0|0A→B1|1确定化、最小化后DFA为：SB0A110Z010,1第26页补充：结构一右线性文法，使它与以下文法等价：

S→ABA→UTU→a|aUT→b|bTB→c|cB

并依据所得右线性文法，结构出对应状态转换图。思绪：先写出原文法所描述语言L(G)={ambnck|m,n,k≥1}G[S]:

S→aS|aBB→bB|bCC→cC|caSaCbcBbcT第27页chapter44.1、考虑下面文法G1：S→a|∧|（T）

T→T，S|S（1）消去G1左递归；S→a|∧|（T）T→ST’T’→，ST’|ε（2）经改写后文法是否是LL(1)文法，给出预测分析表。经改写后文法满足3个条件，所以是LL(1)第28页预测分析表结构算法:1.对文法中每个产生式A→α执行第二步和第三步;FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={),,,#}

FOLLOW(T)={)}

FOLLOW(T)={)}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’T’→ε第29页预测分析表结构算法:1.对文法中每个产生式A→α执行第二步和第三步;2.对每个终止符a∈FIRST(α),把A→a加到M[A,a]中;S→a;S→∧;S→(T);T→ST’;T’→,ST’T’→εFTRST（a）={a}FIRST（∧）={∧}FIRST（（T））={（}FIRST（ST’）={a，∧，（}FIRST（，ST’）={，}FIRST（ε）={ε}

a∧（，）#S

T

T’

S→aS→∧S→(T)T→ST’T→ST’T→ST’T’→,ST’3.若ε∈FIRST(α),则对于任何b∈FOLLOW(A)把A→α加至M[A,b]中FOLLOW(T’)=FOLLOW(T)={)}T’→ε第30页递归子程序：procedureS;begin ifsym='a'orsym='^' thenabvanceelseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;第31页procedureT;begin S;T’EndprocedureT’;begin ifsym=‘,’thenbenginadvance;S;T’endEndsym:是输入串指针IP所指符号advance:是把IP调至下一个输入符号error:是犯错诊察程序第32页补充题：有文法：

E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/（1）求First、Follow集，判断是否是LL（1）文法？（2）若是结构LL（1）分析表？（3）简述LL（1）分析器工作原理。第33页4.2：有文法：

E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|^（1）求First、Follow集，判断是否是LL（1）文法？（2）若是结构LL（1）分析表？（3）简述LL（1）分析器工作原理。第34页E→TE’E’→ATE’|εT→FT’T’→MFT’|εF→（E）|iA→+|-M→*|/FIRST(M)={*，/}FIRST(A)={+，-}FIRST(F)={(，i}FIRST(T’)={*，/，ε}FIRST(T)={(，i)FIRST(E’)={+，-，ε}FIRST(E)={(，i}FOLLOW(E)={#，)}FOLLOW(E’)={#，)}FOLLOW(T)={+，-，#，)}FOLLOW(T’)={+，-，#，)}FOLLOW(F)={*，/，+，-，#，)}FOLLOW(A)={(，i}FOLLOW(M)={(，i}EE→TE’

E→TE’

E’

E→ATE’E→ATE’

E’→εE’→εTT→FT’

T→FT’

T’

T’->εT’→εT’→MFT’T’→MFT’

T’→εT’→εFF→i

F→（E）

A

A→+A→-

M

M→*M→/

i+-*/（）#第35页P81.2.对文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧1)FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,∧}FIRST(E’)={+,ε}FIRST(T’)=FIRST(T)∪{ε}={(,a,b,∧,ε}FIRST(F’)={*,ε}FOLLOW(E)={#,)}FOLLOW(E’)=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)\ε∪FOLLOW(E)={+,#,)}FOLLOW(T’)=FOLLOW(T)={+,#,)}FOLLOW(F)=FIRST(T’)\ε∪FOLLOW(T)={(,a,b,∧,+,#,)}FOLLOW{F’)=FOLLOW(F)={(,a,b,∧,+,#,)}FOLLOW(P)=FIRST(F’)\ε∪FOLLOW(F)={*,(,a,b,∧,+,#,)}(ab∧+*)#EE→TE’E→TE’ETE’ETE’E’E’+EE’εE’εTTFT’TFT’TFT’TFT’T’T’TT’TT’TT’TT’εT’εT’εFFPF’FPF’FPF’FPF’F’F’εF’εF’εF’εF’εF’F’F’εF’εPP(E)PaPbP^第36页2)考虑以下产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.第37页(ab∧+*)#EE→TE’E→TE’ETE’ETE’E’E’+EE’εE’εTTFT’TFT’TFT’TFT’T’T’TT’TT’TT’TT’εT’εT’εFFPF’FPF’FPF’FPF’F’F’εF’εF’εF’εF’εF’F’F’εF’εPP(E)PaPbP^3)預測分析表：第38页4)程序procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance;Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerrorend 第39页procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance;F'endend第40页procedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance;E; ifsym=')'thenadvance elseerror end elseerrorend;第41页4.3下面文法中，那些是LL(1)文法，說明理由结构不带回溯自上而下分析文法条件

1.文法不含左递归，

2.对于文法中每一个非终止符A各个产生式候选首符集两两不相交。即，若A→1|2|…|n

则FIRST(i)∩FIRST(j)＝

(ij)3.对文法中每个非终止符A，若它存在某个候选首符集包含，则FIRST(A)∩FOLLOW(A)=

假如一个文法G满足以上条件，则称该文法G为LL(1)文法。 第42页4.3.1SAbcAa|Bb|是，满足三个条件4.3.2SAbAa|B|Bb|对于A不满足条件34.3.3SABBAAa|Bb|A、B都不满足条件34.3.4SaSe|BBbBe|CcCe|d满足条件3第43页解題思绪：構造文法預測分析表，通常應當按以下步驟進行：

1.消除文法左遞歸（包含全部直接左遞歸和間接左遞歸）

2.對消除左遞歸后文法，提取公因子

3.對經過上述改造后文法，計算它每個非終結符FIRST集合和FOLLOW集合；

4.根據FIRST集合和FOLLOW集合構造預測分析表：第1步對文法G每個產生式Aα執行第1步和第3步；第2步對每個終結符a∈FIRST(α),把Aα加至M[A,a]中；第3步若∈FIRST(α),則對任何b∈FIRST(A),把Aα加至M[A,b]中；第4步把全部無定義M[A,a]標上“出錯標誌”4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程第44页4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程解答：FIRST(Expr)={-,(,id}FOLLOW(Expr)={),#}FIRST(ExprTail)={-,}FOLLOW(ExprTail)={),#}FIRST(Var)={id}FOLLOW(Var)={-,),#}FIRST(VarTail)={(,}FOLLOW(VarTail)={-,),#}第45页4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id--id((id))分析過程-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail第46页-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式0#Exprid--id((id))#開始1#ExprTailvarid--id((id))#ExprVarExprTail2#ExprTailvarTailidid--id((id))#VaridVarTail3#ExprTailvarTail--id((id))#出棧，輸入串後移4#ExprTail--id((id))#VarTail5#Expr---id((id))#ExprTail-Expr(2)給出對句子id--id((id))分析過程第47页-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式5#Expr---id((id))#ExprTail-Expr6#Expr-id((id))#出棧，輸入串後移7#Expr--id((id))#Expr-Expr8#Exprid((id))#出棧，輸入串後移9#ExprTailVarid((id))#ExprVarExprTail10#ExprTailVarTailidid((id))#VaridVarTail11#ExprTailVarTail((id))#出棧，輸入串後移(2)給出對句子id--id((id))分析過程第48页-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式11#ExprTailVarTail((id))#出棧，輸入串後移12#ExprTail)Expr(((id))#VarTail(Expr)13#ExprTail)Expr(id))#出棧，輸入串後移14#ExprTail))Expr((id))#Expr(Expr)15#ExprTail))Exprid))#出棧，輸入串後移16#ExprTail))ExprTailVarid))#ExprVarExprTail17#ExprTail))ExprTailVarTailidid))#VaridVarTail(2)給出對句子id--id((id))分析過程第49页-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTailExprTailVarVaridVarTailVarTailVarTailVarTail(Expr)VarTailVarTail步驟符號棧輸入串所用產生式17#ExprTail))ExprTailVarTailidid))#VaridVarTail18#ExprTail))ExprTailVarTail))#出棧，輸入串後移19#ExprTail))ExprTail))#VarTail20#ExprTail))))#ExprTail21#ExprTail))#出棧，輸入串後移22#ExprTail#出棧，輸入串後移23##ExprTail成功(2)給出對句子id--id((id))分析過程第50页chapter51、令文法G1为：

E→E+T|TT→T*F|FF→(E)|i

证实E+T*F是它一个句型，指出这个句型全部短语、直接短语和句柄。EE+TT*FT*F是句型E+T*F相对于T短语E+T*F句型E+T*F相对于E短语T*F是句型E+T*F相对于T直接短语T*F是句柄第51页2、考虑下面表格结构文法G2：

S→a|^|(T)

T→T,S|S（1）给出(a,(a,a))和(((a,a),^,(a)),a)最左和最右推导。(a,(a,a))最左推导：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))(((a,a),^,(a)),a)最左推导：S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)第52页(((a,a),^,(a)),a)最右推导：S(T)(T,S)(S,S)(S,a)((T),a)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)(a,(a,a))最右推导：S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))第53页2）指出(((a,a),^,(a)),a)规范归约及每一步句柄。S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSa句型句柄归约规则(((a,a),^,(a)),a)aS→a(((S,a),^,(a)),a)ST→S(((T,a),^,(a)),a)aS→a(((T,S),^,(a)),a)T,ST→T,S(((T),^,(a)),a)(T)S→(T)((S,^,(a)),a)ST→S((T,^,(a)),a)^S→^((T,S,(a)),a)T,ST→T,S((T,(a)),a)aS→a((T,(S)),a)ST→S((T,(T)),a)(T)S→(T)((T,S),a)T,ST→T,S((T),a)TS→(T)(S,a)ST→S(T,a)aS→a(T,S)T,ST→T,S(T)(T)S→(T)S第54页依据这个规范规约，给出“移进—归约”过程，并给出它语法树自下而上结构过程。#符号栈输入串：(((a,a),^,(a)),a)#S(T)T,Sa(T)ST,ST,S(T)Sa^(T)ST,SaSa(((aS,TaSS)T,^ST(aST)S)ST,aST)S归约规则句柄aS→aST→SaS→aT,ST→T,S(T)S→(T)ST→S^S→^T,ST→T,S第55页3、(1)计算练习2文法G2FIRSTVT和LASTVT。

G2：S→a|^|(T)

T→T,S|SFIRSTVT(S)={a，∧，(}FIRSTVT(T)={，，a，∧，(}LASTVT(S)={a，∧，)}LASTVT(T)={，，a，∧，)}S→（T）（）.T→T，S

，FIRSTVT(S)﹤.，a,，∧,

，(

﹤.﹤.﹤.T→T，SLASTVT(T)，﹥.a，,∧，,），,，，﹥.﹥.﹥.﹥.S→（T）(FIRSTVT(T)﹤.(a,(∧,((,(，﹤.﹤.﹤.﹤.S→（T）LASTVT(T))﹥.a),∧),)),，)﹥.﹥.﹥.﹥.对待特殊地#,把它看作句型开始和结束符.依据#S#同理可得#a,#∧,#(,﹤.﹤.﹤.##.a#,∧#,）#,﹥.﹥.﹥.#,)(^a#,)(^a=.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.<.=.1、文法是算术文法，且不含ε产生式。2、由优先关系矩阵可知，任何两个终止符之间优先关系不多于一个。综上，该文法是算术优先文法。第56页﹤.

，a∧（）#，

a

∧

(

)

#

﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹥.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤.﹤...输入串(a,(a,a))算符优先过程。步骤句型优先关系最左素短语规约符号1#(a,(a,a))##2345678﹤.(﹤.a﹥.,﹤.(﹤.a﹥.,﹤.a﹥.)﹥.)﹥.#aS#(S,(a,a))#﹤