编译原理陈意云_课后答案2[1].ppt

编译原理习题课 2 栾俊luanj 1 25 2020 2020 1 25 luanj 2 3 1 考虑文法S L aL L S S a 建立句子 a a a 和 a a a a a 的分析树 b 为 a 的两个句子构造最左推导 c 为 a 的两个句子构造最右推导 d 这个文法产生的语言是什么 2020 1 25 luanj 3 3 1 续 a a a S L L S S S a S a L a L S a S S a a S a a a S L L S L L L L S L L a L S a L a a S a a a a a 2020 1 25 luanj 4 3 1 续 a a a a a S L L S S a S L L S S S a S a L a L S a S S a L S a L S S a S S S a a S S a a a S a a a L a a a L S a a a S S a a a a S a a a a a L L S S S L L S L L L L S L L L L L L S L L L a L L S a L L a a L S a a L L a a L L S a a L L a a a L S a a a L a a a a S a a a a a a a a a 2020 1 25 luanj 5 3 1 续 描述的语言 括号匹配的串 串中的各项由 隔开 项可以是括号匹配的子串或a 2020 1 25 luanj 6 3 2 考虑文法S aSbS bSaS a 为句子abab构造两个不同的最左推导 以说明此文法二义 b 为abab构造对应的最右推导 c 为abab构造对应的分析树 d 这个文法产生的语言是什么 2020 1 25 luanj 7 3 2 续 1 S aSbS abS abaSbS ababS abab 2 S aSbS abSaSbS abaSbS ababS ababS aSbS aSb abSaSb abSab abab 2 S aSbS aSbS S aSbS bSaS 1 2 描述的语言是a b数目相等的串 2020 1 25 luanj 8 3 4 文法R R R RR R R a b产生字母表 a b 上所有不含 的正规式该文法是二义的 a 证明该文法产生字母表 a b 上的所有正规式 b 为该文法写一个等价的非二义文法 c 按照上面的两个文法构造ab b a的分析树 2020 1 25 luanj 9 3 4 续 证明该文法产生字母表 a b 上的所有正规式证明 1 该文法产生的串是字母表 a b 上的正规式R a和R b产生a b 而a b是 a b 上的符号 因此是正规式 若R1 R2产生正规式 则 R R1R2产生正规式 R R1 R2产生正规式 R R1 产生正规式 R R1 产生正规式 2 字母表 a b 上的所有正规式都可由此文法产生字母表 a b 上的任一正规式 其中 为正规式 必为以下形式之一 可由R RR产生 可由R R R产生 可由R R 产生 可由R R 产生a 可由R a产生b 可由R b产生因而 该文法产生字母表 a b 上的所有正规式 2020 1 25 luanj 10 3 4 续 该文法没有体现运算符 并置的优先级 因而是二义的 R R R a R a R a b R R R R a R a b E E T TT TF FF F E a bE E T E F E F E b T b F b a b 2020 1 25 luanj 11 3 4 续 ab b a 二义的非二义的 R R R RR a b RR a R b R RR a R R R b RR b a E E T TF T TF F a b F F b a 2020 1 25 luanj 12 3 5 下面的条件语句文法stmt ifexprthenstmt matched stmtmatched stmt ifexprthenmatched stmtelsestmt other试图消除悬空else的二义性 请证明此文法仍是二义的 2020 1 25 luanj 13 3 5 续 由于matched stmt不能保证then和else的配对 因而存在二义性句型ifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmt存在两个不同的最左推导期望的是 ifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmt 2020 1 25 luanj 14 3 5 续 一种推导 和期望的不一样stmt matched stmt ifexprthenmatched stmtelsestmt ifexprthenifexprthenmatched stmtelsestmtelsestmt ifexprthenifexprthenmatched stmtelseifexprthenstmtelsestmt ifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmtifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmt 2020 1 25 luanj 15 3 5 续 另一种推导stmt ifexprthenstmt ifexprthenmatched stmt ifexprthenifexprthenmatched stmtelsestmt ifexprthenifexprthenmatched stmtelsematched stmt ifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmtifexprthenifexprthenmatched stmtelseifexprthenmatched stmtelsestmt 2020 1 25 luanj 16 3 8 a 消除3 1的左递归 2020 1 25 luanj 17 3 8 a 续 S L aL L S S只有直接左递归S L aL SL L SL 2020 1 25 luanj 18 3 10 构造下面文法的LL 1 分析表D TLT int realL idRR idR 2020 1 25 luanj 19 3 10 续 先计算FIRST和FOLLOWFIRST D FIRST T int real FIRST L id FIRST R FOLLOW D FOLLOW L FOLLOW T id FOLLOW R 2020 1 25 luanj 20 3 10 续 2020 1 25 luanj 21 3 11 下面文法是否LL 1 文法 说明理由S AB PQxA xyB bcP dP Q aQ 2020 1 25 luanj 22 3 11 续 不是LL 1 文法LL 1 文法 对于产生式A 本题中 FIRST AB x FIRST PQx d a x 不满足条件 1 2020 1 25 luanj 23 3 15 a 用3 1的文法构造 a a a 的最右推导 说出每个右句型的句柄 b 给出对应 a 的最右推导的移进 归约分析器的步骤 c 对照 b 的移进 归约 给出自下而上构造分析树的步骤 2020 1 25 luanj 24 3 15 续 a b S L L S L L L L S L L a L S a L a a S a a a a a 2020 1 25 luanj 25 3 15 续 a b 续上表 S L L S L L L L S L L a L S a L a a S a a a a a 2020 1 25 luanj 26 3 15 续 a b 续上表 S