编译原理复习(有答案)
素和 FIRST(Yi)都包含在 FIRST(X)中 (e) 当 (d) 中 所 有 Yi 则 ∪FIRST(Yn)∪{} 计算 FOLLOW(A): (a) 设 S 为文法中开始符号,把{#} 加入 FOLLOW(S)中(这里“#”为句子括号)。 (b) 若 A→ B 是 一 个 产 生 式 , 则把 FIRST()的非空元素加入 FOLLOW(B)中。 如果 FOLLOW(B)中。 计算 SELECT(A->): A→, A∈VN, ∈V ,
DFA 的状态图:
正规式与 NFA 的相互转换
例:构造正规式 1(0|1)*101 相应的 DFA 答:先构造 NFA:
生 式 X→Y1Y2…Yn; 当 Y1Y2…Yi-1 都 时 ,( 其 中 1≤i≤n),
则 FIRST(Y1) 、
FIRST(Y2) 、 … 、 FIRST(Yi-1) 的所有非 { } 元
*
各候选式的 FIRST 集,各非终结符的 FOLLOW 集 为 .产 生 式 S→ PS' S'→ aPS' → fS' → P→ qP' P' → bP {b} {a,f,#}
, (i=1, 2, …n),
FIRST(X)=FIRST(Y1) ∪ FIRST(Y2) ∪ …
SELECT FOLLOW 集 {q} {a} {f} {#} {q} {a,f,#} 集 {#} {#}
第六章 自底向上优先分析 算符文法的定义 如果不含空产生式的上下文无关文法 G 中没有形如 A…BC…的产生式, 其中 B, C ∈VN,则称 G 为算符文法(OG) 。 最左素短语的概念 设有文法 G[S],其句型的素短语是一个短 语,它至少包含一个终结符,且除自身外 不再包含其他素短语。处于句型最左边的 素短语为最左素短语 例: 给定文法 G 如下: E→E+T|T; T→T*F|F; F→P↑F|P;P→(E)|i 句型 P*P+i 的最左素短语为( A ) 。 A. P*P ; C. P+i; 第七章 LR 分析 LR(K)的含义 D. P*P+i B. P ;
例: (
A. 词法分析器; C. 语法分析程序; 4. 遍的概念
对源程序(或其中间形式)从头至尾扫描一次并进行 有关加工处理,生成新的中间形式或最终目标程序, 称为一遍。 5. 编译程序与解释程序的区别 D ) 。 B. 对用户程序的差 例:解释程序和编译程序是两类程序语言处理程序, 它们的主要区别在于( 错能力 C. 机器执行效率 码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例:(ab|b) c 与下面的那些串匹配?( ACD )
L R K 号
从左至右扫描输入符号串 构造一个最右推导的逆过程 向右顺序查看输入串的 K 个符
状态 (State) a
Action Goto d #
LR 分析器的逻辑结构及活前缀等概念 LR 分析对文法的要求 构造 LR(0)分析表、SLR(1)分析表 用 SLR 分析法分析非二义性的文法和二义性 的文法。 例:已知文法 A→aAd|aAb| 判断该文法是否是 SLR(1)文法,若是构造 相应分析表,并对输入串 ab#给出分析过 程。 答:文法: A→aAd|aAb|ε 拓广文法为 G′,增加产生式 S′→A 若产生式排序为: 0 1 2 3 S' →A A →aAd A →aAb A →ε 0 1 2 3 4 5
例:已知文法 G[S] S→aB|bA A→a|aS|bAA B→aBB|bS|b 句型 aabbAb 的句柄是( D ) A.a 第四章 词法分析 词法输出的 token 表示法 词法记号、模式、词法单元的概念 词法输出的 token 表示 : 二元式表 示(单词种别,单词自身的值) 例:扫描器的任务是从 别出一个个 单词 。 正规式的概念及其代数性质 源程序 中识 B.ab C.b D.bA
∪FOLLOW(A) 例: 文法: S→iCtS|iCtSeS|a, C→b 中 first(S) 为( A ) ,follow(S)为( B ) 。 A. {i,a}; C. {i,e,#}; LL(1)文法的条件 例:LL(1)文法的条件是___C___。 A. B. 若 C. 对形如 U::=x1 | x2 | … | xn 的规则, 对形如 U::=x1 | x2 | … | xn 的规则, xi=>* , a 和 b 则 要 求 First(xj)∩ 要求 First(xi)∩ First(xj)=,(i≠j); B. {e,#}; D. {e,b}
Follow(U)=,(i≠j) D. 都不是 构造 LL(1)分析表 S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL(1)文法, 并给出 LL(1) 分析表。 答:改造后的文法: S → PS' S' → aPS'| fS' | P → qP' P' → bP | 例:已给文法 G[S] :
则把 FOLLOW(A) 也加入
若 若
,则 SELECT(A→)=FIRST() ,则 SELECT(A→)=(FIRST()-{})
→ { a,f,#} LL(1) 分析表为 a S S' P P' bP aPS' fS' qP' b f q PS' #
QUZ VZ QUZ 重新命名状态子集,令 VQ 为 A、QU 为 B、VZ 为 C、V 为 D、QUZ 为 E、Z 为 F。 . S A B C D E F 0 A C D F F C F 1 B B E F . E F
DFA 的状态图::
第五章 自顶向下语法分析方法 语法分析常用的方法是__B___。 ① 自顶向下 ④ 自右向左 A.①②③④ D.①②③ 会求 FIRST、FOLLOW 集 计算 FIRST(X): (a) 若 X∈VT, 则 FIRST(X)={X} (b) 若 X∈ VN, 且有产生式 X→a…, a∈ VT, 则 a∈FIRST(X) (c) 若 X∈VN, X→, 则∈FIRST(X) (d) 若 X ∈ VN, Y1, Y2, …, Yi ∈ VN, 且有产 B.①② C.③④ ② 自底向上 ③ 自左向右
例:令文法 G[E]为:
xyyxyxyxxy
用子集法将 NFA 确定化 . NFA 和 DFA 的相互转换 例:将下图确定化: X A 0 . 1 A
A AB
AB AC AB AC A ABY ABY AC AB 除 X,A 外,重新命名其他状态,令 AB 为 B、AC 答:用子集法将 NFA 确定化: . 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z V Z Z Z Z . Z 为 C、ABY 为 D,因为 D 含有 Y(NFA 的终态), 所以 D 为终态。 . X A B C D 0 . A C A C 1 A B B D B
词法分析中的单词符号的描述工具 正规式代表的集合 例: 请描述下面正规式定义的串,字母表 S = {0, 1}。 1(0|1)*0 答:必须以 1 开头 0 结尾的串 例:为下边所描述的串写正规式,字母表是 {0, 1}。 以 01 结尾的所有串 答:(0|1)*01 正规文法和正规式相互转换 正规文法到正规式的转换规则: 正规文法 A xB, B y A=xy A xA y A=xy A x, A y A=xy 例:给出下述文法所对应的正规式: S→0A|1B A→1S|1 B→0S|0 答: S->0A | 1B ->01S | 01 | 10S | 10 ->(01|10)S | (01|10) -> (01|10) (01|10)* (01|10) (01|10)* NFA 和 DFA NFA 和 DFA 的组成 例:指出哪些串是自动机可接受的 (②④) xy ② xyxxy ③ yyyx ④ 即 : r= 转换成: 转换成: 正规式 转换成:
例:文法 S→abC|c,bC→d 是几型文法?0 型 例:文法 S→abC,bC→ad 是几型文法?1 型 例: 文法 G[A]: A→, A→aB, B→Ab, B→a 是几型文法?2 型 例:文法 S→a|bC , C→d 是几型文法? 3
型 最左(右)推导 规范推导 :最右推导被称为规范推导 规范句型 :由规范推导所得的句型称为规范句型 规范归约:左归约为规范归约 二义性 二义的 。 例:如果一个文法存在某个句子对应两棵不同的语 法树,则称这个文法是 ( 例 : 已 知 文 法 G1 : P->PaP|PbP|cP|Pe|f , G1 是 A ) 。 A 二义文法;B 无二义的 例:证明下述文法 G[<表达式>]是二义的。 < 表达式>→a|(< 表达式>)|<表达式>< 运算符>< 表达 式> <运算符>→+|-|*|/ 答:可为句子 a+a*a 构造两个不同的最右推导: 最右推导 1 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈表达式〉 〈运算符〉a 〈表达式〉* a 〈表达式〉 〈运算符〉 〈表达式〉* a 〈表达式〉 〈运算符〉a * a 〈表达式〉+ a * a a+a*a 最右推导 2 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈运算符〉 〈表 达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈运算符〉 a 〈表达式〉 〈运算符〉 〈表达式〉 * a 〈表达式〉 〈运算符〉a * a 〈表达式〉+ a * a a+a*a 短语、句柄、直接短语 E->E+T|E-T T->T*F|T/F|F F->(E)|i 证明 E+T*F 是它的一个句型 , 指出这个句型的所有 短语、直接短语和句柄。