nj@
23
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))
栈
$
• 下面文法是否LL(1)文法？说明理由 S -> AB|PQx A -> xy B -> bc P -> dP|ε Q -> aQ|ε
2018/10/21
luanj@
21
3.11 (续)
• 不是LL(1)文法 • LL(1)文法：对于产生式A->α|β (1) FIRST ( ) FIRST ( )
• (1) S=>aSbS=>abS=>abaSbS=>ababS=>abab (2) S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab • S=>aSbS=>aSb=>abSaSb=> abSab =>abab (2)
S a S ε b a S ε (1) 描述的语言是a,b数目相等的串 S b S ε S
2018/10/21 luanj@ 14
3.5 (续)
• 另一种推导
stmt => if expr then stmt => if expr then matched_stmt => if expr then if expr then matched_stmt else stmt => if expr then if expr then matched_stmt else matched_stmt => if expr then if expr then matched_stmt else if expr then matched_stmt else stmt if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
a S
b S ε (2) a
b
S ε
S
ε
2018/10/21
luanj@
7
3.4
• 文法 R->R’|’R | RR | R* | (R) | a | b 产生字母表(a, b)上所有不含ε的正规式 该文法是二义的 (a) 证明该文法产生字母表{a,b}上的所有正 规式 (b) 为该文法写一个等价的非二义文法。 (c) 按照上面的两个文法构造ab|b*a的分析 树
S ( L S a L S L , ) S
(
L
, (
)
S L , ) S
(
L S
L
,
)
S a
L S a
a
2018/10/21
luanj@
4
a
3.1 (续)
• 描述的语言： 括号匹配的串，串中的各项由”,”隔开， 项可以是括号匹配的子串或a
2018/10/21
luanj@
luanj@ 9
2018/10/21
3.4 (续)
• 该文法没有体现运算符 |、*、() 、并置的优 先级，因而是二义的。
R=>R|R=> a|R =>a|R*=>a|b* R=>R*=>R|R*=>a|R*=>a|b*
• E -> E’|’T | T T -> TF | F F -> F* | (E) | a | b
S
( L S a L , ( L S a
2018/10/21 luanj@ 3
) S L , ) S a
3.1 (续) - (a,((a,a),(a,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))) 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)))
5
3.2
• 考虑文法 S -> aSbS|bSaS|ε (a) 为句子abab构造两个不同的最左推导， 以说明此文法二义 (b) 为abab构造对应的最右推导 (c) 为abab构造对应的分析树 (d) 这个文法产生的语言是什么
2018/10/21
luanj@
6
3.2 (续)
2018/10/21 luanj@ 15
3.8(a)
• 消除3.1的左递归
2018/10/21
luanj@
16
3.8(a) (续)
• S -> (L)|a L -> L,S|S • 只有直接左递归 S -> (L)|a L -> SL’ L’-> ,SL’|ε
2018/10/21 luanj@ 8
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}上的所有正规式
期望的是： if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
2018/10/21
luanj@
13
3.5 (续)
• 一种推导，和期望的不一样
stmt => matched_stmt => if expr then matched_stmt else stmt => if expr then if expr then matched_stmt else stmt else stmt => if expr then if expr then matched_stmt else if expr then stmt else stmt => if expr then if expr then matched_stmt else if expr then matched_stmt else stmt if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
2018/10/21
luanj@
19
3.10 (续)
int D T
D -> TL
real
D -> TL
id
,
$
T -> int
T -> real
L
R
2018/10/21
L -> idR R -> ε
20
R -> ,idR
luanj@
3.11
$( $(a $(S
输入
(a,(a,a))$ a,(a,a))$ ,(a,a))$ (a,a))$
动作
移进
移进 归约:S->a 归约:L->S
$(L
$(L, $(L,( $(L,(a
,(a,a))$
(a,a))$ a,a))$ ,a))$
luanj@
2018/10/21 luanj@ 2
3.1 (续) - (a,(a,a))
S =>(L) S =>(L) =>(L,S) =>(L,S) =>(S,S) =>(L,(L)) =>(a,S) =>(L,(L,S)) =>(a,(L)) =>(L,(L,a)) =>(a,(L,S)) =>(L,(S,a)) =>(a,(S,S)) =>(L,(a,a)) =>(a,(a,S)) =>(S,(a,a)) =>(a,(a,a)) =>(a,(a,a))
(2)若 * ，那么FIRST ( ) FOLLOW ( )