Microsoft PowerPoint - 5-BottomUpParsing12.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 5-BottomUpParsing12.ppt [兼容模式]"

锄孔
5 years ago
Views:

1 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 第五章自下而上的语法分析第五章自下而上的语法分析规范归约概念算符优先分析 LR 分析法赵银亮自下而上分析基本问题自下而上的分析过程推导的逆过程 : 归约给定 oken 串输入串 ), 逐步归约, 最后归约成文法开始符号, 表示分析成功过程中可以产生结果, 如生成语法树语法分析栈 # 输入串动作 InputString# 移进 Shift) 归约 Reduce) 语法分析栈 S # # 输入串接受 Accept) 1

2 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 2

3 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 3

4 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 4

5 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 5

6 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 6

7 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 7

8 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 以上分析过程的另一种表示文法 G xpr xpr Op xpr xpr xpr) xpr - xpr xpr num Op Op - Op * InputString num * num num ) Parsing Stack Input String Action # num*numnum)# shift #num *numnum)# shift #xpr *numnum)# reduce xpr num #xpr* numnum)# shift #xpr Op numnum)# reduce Op * #xpr Op numnum)# shift #xpr Opnum num)# shift #xpr Opxpr num)# reduce xpr num #xpr Opxpr num)# shift #xpr Opxpr Op num)# reduce Op #xpr Opxpr Op num )# shift #xpr Opxpr Op xpr )# reduce xpr num #xpr Opxpr )# reduce xpr xpr Op xpr #xpr Opxpr) # shift #xpr Op xpr # reduce xpr xpr) #xpr # reduce xpr xpr Op xpr 观察输入串中的当前 oken 被移进栈, 即 Push 到栈顶, 当前 oken 指向下一个如果栈顶部分的符号串刚好跟某个非终结符 A 的一个候选式一样, 则这部分全部出栈, 然后将 A 压入栈这个过程即是归约归约所产生的动作为输出该产生式或者构造语法树分析的初始状态接受状态出错状态分析过程中可能出现冲突 : op of the stack may match RHS of multiple productions But that may not be the right match May need to shift an input and later find a different reduction 8

9 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 9

10 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 10

11 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 11

12 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 12

13 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 13

14 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 14

15 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 观察当前栈顶部分与多个产生式右部匹配 ; 移进归约冲突反映了文法有二义性 ; 通过消除文法二义性可以避免某些移进归约冲突 ; 通过向前查看一个 oken 可以避免某些移进归约冲突 ; 5.2 规范归约短语 : 给定文法 G, S 是 G 的开始符号, 设 αβδ 是 G 的一个句型, 那么, 如果有 S =>* αaδ 且 A => β, 则称 β 是句型 αβδ 相对于非终结符 A 的短语直接短语 : 如果有 A=> β, 则称 β 是句型 αβδ 相对于规则 A β 的直接短语 15

16 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例 : 短语直接短语例 : 短语直接短语 S S *i /i i 2 是句型 2-3*4 相对于和的短语, 是相对于 i 的直接短语 S 2 是句型 2*34 相对于的短语, 是相对于 i 的直接短语 2 - * *4 3 是句型 2-3*4 相对于的短语, 是相对于 i 的直接短语 3*4 是句型 2-3*4 相对于的短语, 不是直接短语 2-3*4 是句型 2-3*4 相对于和 S 的短语, 不是直接短语 2*34 * S *i /i i 4 是句型 2*34 相对于的短语, 是相对于 i 的直接短语 2*3 是句型 2*34 相对于和的短语, 不是直接短语 2-3*4 是句型 2*34 相对于和 S 的短语, 不是直接短语规范归约续 ) 句柄 : 一个句型的最左直接短语称为该句型的句柄例 : S *i /i i S 句型 : 2-3*4 2 是句型 2-3*4 相对于和的短语, 是相对于 i 的直接短语, 是句柄 2 - * 是句型 2-3*4 相对于的短语, 是相对于 i 的直接短语 3*4 是句型 2-3*4 相对于的短语, 不是直接短语 2-3*4 是句型 2-3*4 相对于和 S 的短语, 不是直接短语 16

17 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例 : S *i /i i S 句型 : 2*34 2 是句型 2*34 相对于的短语, 是相对于 i 的直接短语, 是句柄规范归约续 ) 规范归约 : 是关于给定句型的一个最右推导的逆过程, 也称最左归约 * 是句型 2*34 相对于的短语, 是相对于 i 的直接短语 2*3 是句型 2*34 相对于和的短语, 不是直接短语 2-3*4 是句型 2*34 相对于和 S 的短语, 不是直接短语最右推导 : 从文法开始符号开始, 每一次直接推导中总是将当前句型中最右边的那个非终结符应用它的产生式规则变成下一个句型, 也称为规范推导规范句型 : 由规范推导所得的句型称为规范句型 ; 规范归约续 ) 假定 α是文法 G的一个句子, S是 G的开始符号, 称序列 α, α,..., α是 α的一个规范规约, 0 n 1 1 1) α = α, α = S; n n 如果此序列满足 : 2) 对任意 0< i n, α 是对 α将其句柄替换为 i 1 相应产生式左部而得. i 例 : S - -*i -i*i -i*i i-i*i i-i*i -i*i -i*i -*i - S S - * 4 句子 : 2-3*4 S *i /i i

18 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例 : S *i /i i S 句子 : 2*34 S=>=>=>i =>i=>*ii=>i*ii 例 5.1 文法 G2: S->aAcBe A->b A->Ab B->d 输入串 :abbcde * 3 4 i*ii<=*ii<=i <=i <=<=<=S 最右推导 : S => aacbe => aacde => aabcde 最左归约 : => abbcde 2 abbcde <= aabcde <= aacde <= aacbe <= S 规范归约 : 规范归约 : abbcde <=aabcde <=aacde <=aacbe <=S abbcde <=aabcde <=aacde <=aacbe <=S S S a A c B e a A c B e A b d 文法 G2: A b d 文法 G2: b 语法分析树 S->aAcBe A->b A->Ab B->d b 语法分析树 S->aAcBe A->b A->Ab B->d 18

19 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 规范归约 : 规范归约 : abbcde <=aabcde <=aacde <=aacbe <=S abbcde <=aabcde <=aacde <=aacbe <=S S S a A c B e a A c B e A b d 文法 G2: A b d 文法 G2: b S->aAcBe A->b S->aAcBe A->b 语法分析树 A->Ab B->d 语法分析树 A->Ab B->d 规范归约 : 规范归约 : abbcde <=aabcde <=aacde <=aacbe <=S abbcde <=aabcde <=aacde <=aacbe <=S S S a A c B e a A c B e A b d 文法 G2: d 文法 G2: S->aAcBe A->b S->aAcBe A->b 语法分析树 A->Ab B->d 语法分析树 A->Ab B->d 19

20 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 规范归约 : 规范归约 : abbcde <=aabcde <=aacde <=aacbe <=S abbcde <=aabcde <=aacde <=aacbe <=S S S a A c B e a A c B e d 文法 G2: 文法 G2: S->aAcBe A->b S->aAcBe A->b 语法分析树 A->Ab B->d 语法分析树 A->Ab B->d 规范归约 : 规范归约 : abbcde <=aabcde <=aacde <=aacbe <=S abbcde <=aabcde <=aacde <=aacbe <=S S S a A c B e 文法 G2: 文法 G2: S->aAcBe A->b S->aAcBe A->b 语法分析树 A->Ab B->d 语法分析树 A->Ab B->d 20

21 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 符号栈的使用与语法树的表示分析栈符号栈 ) # 分析栈符号栈 ) 输入串 InputString# 输入串动作移进 Shift) 归约 Reduce) 出错 5.4 LR 分析法 LR 分析的思想构造 DFA 控制 shift 和 reduce 动作由 DFA 构造分析表 LR0) 与 SLR1) S # # 接受 Accept) 状态栈 s 0 s 0 s 1 s m LR 分析的思想符号栈 # 动作 #X 1 X 2 X l 输入串 a 1 a 2 a n # a i a i1 a n # 动作将符号和状态分别进栈 ; 根据给定的产生式归约 ; 接受 ; 根据当前符号和当前状态决定动作每个动作指明了下一个状态是什么 LR 分析的思想续 ) Stack Input Action # ))# shift # ))# shift # ))# shift #) )# reduce X ) #X )# shift #X) # reduce X X) #X # reduce S X #S # accept S X X X) X ) 如何确定句柄? 历史展望当前符号规范句型活前缀用 DFA 来实现活前缀 : 规范句型的一个前缀任意首部 ) 该前缀是不含句柄之后的任何符号 21

22 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University LR0) 项目集需要知道对于给定的产生式我们到目前为止已经扫描过了多少? X X ) 文法 : 在这儿? 在这儿? 在这儿? S X 在这儿? X X) X ) 由此生成 4 个项目 X X ) X X ) X X ) X X ) 例 : 文法与项目 S X# S X # X X ) S X# X X ) X X) X X ) X ) X X ) X ) X ) X ) 解决思路项目中的关键点 Stack Input Action # ))# shift # ))# shift # ))# shift #) )# reduce X ) #X )# shift #X) # reduce X X) #X # reduce S X #S # accept S X# X X) X ) 项目 S X# S X # X X ) X X ) X X ) X X ) X ) X ) X ) 状态对应于项目集若状态包含项目 A α c β 分析程序期望最终采用产生式 A αc β 进行归约分析程序已经扫描了 α 期望输入流能够包含 c, 然后 β 若状态包含项目 A α 分析程序已经扫描了 α 将使用 A α 进行归约若状态包含项目 S α # 并且输入串为空分析程序接受该输入 22

23 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 项目与行为的相互关联构造 NFA 识别活前缀如果当前状态包含项目 A α c β 并且当前输入符号是 c 分析程序将 c 移到栈顶 Shift 会包含 A αc β 如果当前状态包含项目 A α 分析程序使用 A α 进行归约下一状态? 如果当前状态包含项目 S α # 并且输入串为空分析程序接受该输入 Reduce Accept 每个项目构成一个状态 ; 项目 S S 为 NFA 的唯一初态 ; 从每个状态 X X 1 X i-1 X i X n 到状态 X X 1 X i X i1 X n 画一条标记为 X i 的弧 ; 另外, 若 X i 为非终结符, 那么到所有形如 X i γ 的项目所在的状态画 ε 弧对 NFA 的解释 Shift c A α cη A αc η Reduce, then push N A α Nη A αn η ε N β S X X X) X ) 1S X# 2S X # 3X X ) 4X X ) 5X X ) 6X X ) 7X ) 8X ) 9X ) 例 6X X) ) 5X X ) X 4X X) ε ε 3X X) ε 1S X# X 2S X ε 7X ) 8X ) ) 9X ) 23

24 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University S X X X) X ) S X X ) ) 例 6X X) ) 5X X ) X 4X X) ε ε 3X X) ε 1S X# X 2S X ε 7X ) 8X ) ) 9X ) 6X X) ) NFA 5X X ) X ε 1S X# ε 3X X) X ) 4X X) ε 2S X 7X ) 8X ) 9X ) ε 4X X) 8X ) 3X X) 7X ) 1S X# 3X X) 7X ) ) ) X DFA 9X ) X 5X X ) 6X X) 2S X Action 1 # ))# shift 13 # ))# shift 133 # ))# shift 1334 #) )# reduce X ) 135 #X )# shift 1356 #X) # reduce X X) 12 #X # reduce S X # accept S X X ) ) 3 4X X) 8X ) 3X X) 7X ) 1 1S X# 3X X) 7X ) ) ) X 4 9X ) X 5 5X X ) 6 6X X) 2 2S X LR0) 分析表的构造 DFA: S, Σ, δ, s, F), Σ= V V {#} 0 a V if m n) M[ m, ACION a)]: = sn; X VN if m n) M[ m, GOO X )]: = n; if { A αi} itemset m)) a V, M[ m, ACION a)]: = r k; mn, S; k为规则 A α的编号 ; sn为 shift to n缩写 ; rk为 reduce to k缩写 N 24

25 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University ACION GOO State ) # X 1 s3 2 2 acc 3 s3 s4 5 4 r3 r3 r3 5 s6 6 r2 r2 r2 a V if m n) MmACIONa [, )]: = sn; X VN if m n) M[ m, GOO X )]: = n; if { A αi} itemset m)) a V, M[ m, ACION a)]: = r k; 例 1. 构造分析表 3 4X X) 8X ) 3X X) 7X ) 1 1S X# 3X X) 7X ) ) ) X 4 9X ) X 5 5X X ) 6 6X X) 2 2S X 基于分析表的语法分析输入 : 一个输入串 w 和一个 LR 语法分析表, 这个表描述了文法 G 的 ACION 函数和 GOO 函数输出 : 如果 w 在 LG) 中, 则输出 w 的自下而上语法分析过程中的规约步骤 ; 否则给出错误初始化 : 语法分析器栈中的内容为初始状态 s0, 输入缓冲区中的内容为 w# 分析算法 } else if ACION[s, a]= 归约 A β) { 从栈中弹出 β 个符号 ; 令 t 为当前的栈顶状态 ; 将 GOO[t, A] 压入栈中 ; 输出产生式 A β; } else if ACION[s, a]= 接受 ) break 令 a 为 w# 的第一个符号 ; else 调用错误恢复例程 ; while 1) { } 令 s 是栈顶的状态 ; if ACION[s, a]= 移入 t ) { 将 t 压入栈中 ; 令 a 为下一个输入符号 ; 例 2 构造文法 G 的 LR0) 分析表文法 G S aa bb A ca d B cb d S S aa a A aa bb b B bb A ca 10 A c A 11 A ca 12 A d 13 A d 14 B cb 15 B c B 16 B cb 17 B d 18 B d 25

26 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University ε 5 aa c A A 9A ca 10A c A 11A ca ε ε 4 a A ε a d 12A d 13A d 3 aa ε 1S 2S ε 6 bb d b 17B d ε ε 7 b B B ε c 14B cb 15B c B 8 bb ε 18B d B 16B cb a b c d A B {1,3,6} {4,9,12} {7,14,17} {2} {4,9,12} {9,10,12} {13} {5} {7,14,17} {14,15,17} {18} {8} {2} {9,10,12} {9,10,12} {13} {11} {13} {5} {14,15,17} {14,15,17} {18} {16} {18} {8} {11} {16} a 5 aa 4 1S 3 aa 6 bb 1 b 9 8 bb A 4 a A 9A ca 12A d 3 7 b B 14B cb 17B d B 8 c 10A c A A 11A ca 9A ca 12A d 6 c 5 a V d if m n) 13A d d MmACIONa [, )]: = sn; 7 X VN if m n) 2S M[ m, GOO X )]: = n; d 2 if { A αi} item m)) a V, M[ m, ACION a)]: = r k; d 18B d 11 c 15B c B 14B cb B 17B d 16B cb c ACION 动作 ) GOO 转换 ) 状态 a b c d # A B 1 s3 s8 2 2 acc S 3 s5 s7 4 4 r5 r5 r5 r5 r5 aa 5 s5 s7 6 6 r11 r11 r11 r11 r11 A ca 7 r13 r13 r13 r13 r13 B d 8 s10 s r8 r8 r8 r8 r8 bb 10 s10 s r18 r18 r18 r18 r18 A d 12 r16 r16 r16 r16 r16 B cb 26

27 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University LRk) LR 分析法概貌 L- 从左往右扫描输入串 R- 最右推到的逆过程 K- 向前查看 k 个符号常见的程序语言构造都可以用 LR 分析法 ; 是已知的最通用的无回溯移入 - 规约分析技术 ; 能够尽可能早地检测到错误 ; LR 可分析的文法类是 LL 分析的文法类的真超集 LRk) LR0) LR 分析法概貌 L- 从左往右扫描输入串 R- 最右推到的逆过程 K- 向前查看 k 个符号 SLR 简单 LR 表构造法 ) 规范 LR LALR 向前 LR 表构造法 ) 缺点 : 手工构造 LR 分析器工作量巨大 LR0) 文法任意状态 s 若含有某个完全项 A α, 则不能含有其他任何项目 Shift-Reduce Conflict 若状态 s 含有 shift 项目 A α cβ Reduce-Reduce Conflict 若状态 s 含有另一个完全项目 B γ 文法 G 是 LR0) 的充要条件是 : 当且仅当每个状态是个移进状态只含移进项目 ) 或归约状态只含一个完全项目 ) ε 例 n 4 n n n 5 n 6 n 7 n ε ε 8 n ε n n n n n n n n 27

28 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例 n n 0 n 1 n n n 4 n 5 n 6 n 7 n 8 n n n 2 n 3 n 4 n Reduction-Only Lookahead Parsing 如果某状态包含 A ω Only reduce A ω if the next token t is in FOLLOWA). SLR1) 对于状态 itemset={x α cβ, A α, B α } 1. 若 t=c 则移进 ; 2. 若 t FOLLOWA) 则用 A α 归约 ; 3. 若 t FOLLOWB) 则用 B α 归约 ; 4. 其他则出错例分析表 M 1) n 2) n 3) n 0 n 1 n 3 2 n n ACION GOO State n # 0 s1 3 1 r1 s3/r1 2 r3 r3 r3 3 err err acc n M[1,] 有冲突 FOLLOW ) 故 M[1,]:=s3 SLR1) 分析表对每一个状态消除无用的归约动作 a V if m n) 同 LR0) M[ m, ACION a)]: = sn; a V N if m n) M[ m, GOO X )]: = n; if { A α } item m) c FOLLOW A)) M[ m, ACION c)]: = rk 比 LR0) 强 28

29 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 二义性与冲突 statement if-stmt other if-stmt if exp ) statement if exp ) statement else statement exp 0 1 S I o I if S if S el S S S I if S I if S el S S I S o o S o if S S I if S I if S el S S I S o I if S I if S el S S if I I S I I if S I if S el S el o if I if S el S S I S o I if S I if S el S S I FollowI)={el,#} S o I if S el S 移进优先于归约消除 if 二义性的规则当前输入符号为 el 时, 虽然 el FOLLOWI) 但移进项目 I if S el S 优先 SLR1) 局限性可处理几乎所有使用语言结构局限 : itemset={x α cβ, Y α bγ, A α, B α } S id V:= V id V n FollowS)={#} FollowV)={:=,#} S S S id S V:= V id id S id V id 29

30 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University More General Lookahead 项目集包含潜在的向前查看信息, 产生多个状态项目 A α X β c 下一个输入符号 c 已经分析过 α, 期望分析 X β, 那么用 A α 归约除了当前状态, 所有分析动作是向前查看的符号的函数 S ) S # S S ) ) ) ) ) ) ) # S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # 30

31 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # 31

32 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # 32

33 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University S ) S # # S S ) ) ) ) ) ) S ) S # # S S ) ) ) ) ) ) ) # ) # Constructing LR1) Automata S ) S # # S S ) ) ) ) ) ) ) # Begin with a state S [#]. For each state A [t], for each production A γ: Construct states A α ω [t] for all possible ways of splitting γ = αω. Add an ε-transition from A [t] to each of these states. Add transitions on x between A α xω [t] and A αx ω [t] For each state A α Bω [t], add an ε-transition from A α Bω [t] to B [r] for each terminal r FIRSωt). 33

34 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University S i ) S # S # S # # # # # # ) ) i i ) ) i ) ) ) ) ) ) # # ) ) # )# )# )# ) ) # ) ) ) ) ) ) ) ) ) ) i# i i # i ) i i ) Constructing LR1) Automata II Begin in a state containing S [#], where S is the start symbol. Compute the closure of the state: If A α Bω [t] is in the state, add B γ [t] to the state for each production B γ and for each terminal t FIRSωt) Repeat until no new states are added: If a state contains a production A α xω [t], add a transition on x from that state to the state containing the closure of A αx ω [t]. Deterministic LR1) Automata Representing LR1) Automata As with LR0), use action and goto tables. goto table defined as before; encodes transition table as map from state, token) to states. action table maps pairs state, lookahead) to actions. Commonly combined o a single action/goto table. 34

35 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University he LR1) Parsing Algorithm Begin with an empty stack and the input set to ω#, whereω is the string to parse. Set state to the initial state. Repeat the following: Let the next symbol of input be t. If action[state, t] is shift, then shift the input and set state = goto[state, t]. If action[state, t] is reduce A ω: Pop ω symbols off the stack; replace them with A. Let the state atop the stack be top-state. Set state = goto[top-state, A] If action[state, t] is accept, then the parse is done. If action[state, t] is error, report an error. Constructing LR1) Parse ables For each state X: If there is a production A ω [t], set action[x, t] = reduce A ω. If there is the special production S [#], where S is the start symbol, set action[x, t] = accept. If there is a transition out of s on symbol t, set action[x, t] = shift. Set all other actions to error. If any table entry contains two or more actions, the grammar is not LR1) S i ) ) # 1 s5 s4 s2 2 s6 acc 3 r3 r3 4 r2 r2 5 r5 r5 6 s5 s7 s3 7 s10 s14 s10 s8 8 s9 s12 9 r5 r5 10 r2 r2 11 r4 r4 12 s11 s13 13 r3 r3 14 s11 s14 s10 s15 15 s16 s12 16 r5 r5 P133 1, 51-3), 7, 8 本章作业上机题 B 编写程序输入一个算符优先文法, 自动构造出优先关系表并输出 ), 该程序还能对输入的句子进行语法分析, 依序输出分析过程中归约的最左素短语本题与上一章题目任选一个完成 ) 35

36 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 练习 Basic Idea Behind LR1) Split states in LR0) DFA based on lookahead Reduce based on item and lookahead 作业 27 日交 : P63-65:2,6-9,12,14,15 上机 : 完成上机题 I 并写好报告 Items will keep info on LR1) Items production right-hand-side position the dot) look ahead symbol LR1) item is of the form [A α βc] A β is a production he dot in A α β denotes the position c is a terminal or the end marker #) Meaning of LR1) Items 项目 [A α βc] 含义 he parser has parsed an α If it parses a β and the next symbol is c hen parser should reduce by A αβ 36

37 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例 :LR1) 项目 Creating a LR1) Parser ngine S [ X# )] Need to define Closure) and Goto) functions S X# X X) X ε S [ X# ] S [ X# #] S [X # )] S [X # ] S [X # #] X [ X ) )] X [ X ) ] X [ X ) #] X [ X ) )] X [ X ) ] X [ X ) #] X [X ) )] X [X ) ] X [X ) #] X [X ) )] X [X ) ] X [X ) #] X [ )] X [ ] X [ #] for LR1) items Need to provide an algorithm to create the DFA Need to provide an algorithm to create the parse table Closure algorithm ClosureI) repeat for all items [A α X β c] in I for any production X γ for any d Firstβc) I = I { [X γ d] } until I does not change Goto algorithm GotoI, X) J = { } for any item [A α X β c] in I J = J {[A α X β c ]} return ClosureJ) 37

38 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University Building the LR1) DFA Start with the item [S S #?] Find the closure of the item and make an state Pick a state I for each item [A α X β c] in I find GotoI, X) if GotoI, X) is not already a state, make one Add an edge X from state I to GotoI, X) state Repeat until no more additions possible Creating the parse tables For each LR1) DFA state ransition to another state using a terminal symbol is a shift to that state shift to sn) ransition to another state using a nonterminal is a goto that state goto sn) If there is an item [A α a] in the state, do a reduction for input symbol a with the production A αreduce k) Motivation LALR1) Parser LR1) parse engine has a large number of states Simple method to eliminate states If two LR1) states are identical except for the look ahead symbol of the items then Merge the states Result is LALR1) DFA ypically has many fewer states than LR1) May also have more reduce/reduce conflicts 38

39 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 算符优先文法构造优先关系表算符优先分析算法优先函数 5.3 算符优先分析算符文法和算符优先文法算符文法 : 如果一个文法的任何产生式右部都不含两个相继并列 ) 的非终结符, 即不含有如下形式的产生式右部 : QR 则我们称该文法为算符文法 a b 对算符文法的观察当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 R b 或 R Qb a b 当且仅当 G 中有 P Rb 且 R a 或 R aq 算符优先文法对于不含 ε 产生式的算符文法 G, 如果其中任意一对终结符 a, b) 至多只满足下述三种情况之一 : a b a b a b 则称 G 是一个算符优先文法, 39

40 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 例优先关系表 *F F F P^F P P ) i * ^ i ) # * ^ i ) # a b 当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 R b 或 R Qb a b 当且仅当 G 中有 P Rb 且 R a 或 R aq 构造优先关系表 a b 当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 R b 或 R Qb a b 当且仅当 G 中有 P Rb 且 R a 或 R aq 对每个非终结符 R 求出所有的 b, 其中, R b 或 R Qb R a 或 R aq FIRSVR), LASVR) 构造非终结符的 FIRSV 集和 LASV 集构造优先关系表时, 要找出所有终结符对之间的优先关系, 而对于可以直接检查所有的产生式规则即可得出 ; 而对于和需要在直接检查产生式规则基础上并借助 FIRSV 集和 LASV 集完成 FIRSVP)={a P a 或 P Qa, a V, Q V N } LASVP)={a P a 或 P aq, a V, Q V N } a b 当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 b FIRSVR) a b 当且仅当 G 中有 P Rb 且 a LASVR) 构造集合 FIRSVP) 的算法 P,Q 是文法 G 的非终结符,a 是终结符, 重复直到不变 : 若 G 有产生式 P a 或 P Qa, 则 a FIRSVP) 若 a FIRSVQ), 且有 P Q, 则 a FIRSVP) 设置数组 F 和栈 S; F[P,a] 初始化为 FALS, P V N, a V Foreach 产生式 P a 或 P Qa If!F[P,a]){F[P,a]:=RU; pushs,<p,a>)} While!emptyS)){ <Q,a>:= tops); pops); Foreach 产生式 P Q If!F[P,a]){F[P,a]:=RU; pushs,<p,a>)} } FIRSVP)={a F[P,a]==RU} 40

41 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 构造集合 LASVP) 的算法 P,Q 是文法 G 的非终结符,a 是终结符, 重复直到不变 : 若 G 有产生式 P a 或 P aq, 则 a LASVP) 若 a LASVQ), 且有 P Q, 则 a LASVP) 设置数组 F 和栈 S; F[P,a] 初始化为 FALS, P V N, a V Foreach 产生式 P a 或 P aq If!F[P,a]){F[P,a]:=RU; pushs,<p,a>)} While!emptyS)){ <Q,a>:=topS); pops); Foreach 产生式 P Q If!F[P,a]){F[P,a]:=RU; pushs,<p,a>)} } LASVP)={a F[P,a]==RU} 构造优先表 M a b 当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 b FIRSVR) a b 当且仅当 G 中有 P Rb 且 a LASVR) Foreach 产生式 P X 1 X 2 X n For i:=1; i<n; i){ If X i,x i1 V ) M[X i, X i1 ] := ; If i n-2&&x i,x i2 V && X i1 V N )M[X i, X i2 ]:= ; If X i V && X i1 V N ) foreach a FIRSV X i1 ) M[X i, a] := ; If X i V N && X i1 V ) foreach a LASV X i ) M[a, X i1 ] := ; } 优先表中对 # 的处理增广文法 ) S 是文法 G 的开始符号, 给 G 中添加一个产生式 S #S# 显然 : M[#,#]:= ; foreach a FIRSVS) M[#, a]:= ; foreach b LASVS ) M[b, #]:= ; 例 *F F S ## F P^F P P ) i * ^ i ) # * ^ i ) # a b 当且仅当 G 中有 P ab 或 P aqb a b 当且仅当 G 中有 P ar 且 b FIRSVR) a b 当且仅当 G 中有 P Rb 且 a LASVR) 41

42 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 算符优先分析算法文法 G, β 是句型 αβδ 的一个短语, 若 : 文法 G 的开始符号为 S, 对于 S =>*αβδ, 有 S =>*αaδ 且 A =>β 素短语只针对算符文法 ) 所谓素短语是指这样一个短语, 它至少含有一个终结符, 并且, 除自身之外, 不再含任何更小的素短语最左素短语句型中最左边的那个素短语叫最左素短语定理一个算符优先文法 G 的任何句型 #N 1 a 1 N 2 a 2 N n a n N n1 # 其中 a i V,i=1..n; N i =ε 或者 N i V N, i=1..n1 的最左素短语是满足以下条件的最左子串 N j a j N i a i N i1 其中 a j-1 a j a j a j1,, a i-1 a i # i 1 *i 2 i 3 )# a i a i1 # i 1 * i 2 i 3 ) 对定理的解释句型 #N 1 a 1 N 2 a 2 N n a n N n1 # 记为 αn j a j N i a i N i1 β a j N i a i N i1 由 a j a j1,, a i-1 a i 可知 N j a j N i a i N i1 是某个产生式规则 N j a j N i a i a j N i a i 其左部设为 R) 的候选式 ; 由 a j-1 a j 可知有规范推导最右推导 ): αrβ αn j a j N i a i N i1 β 由 a i a i1 可知有规范推导 : αrβ αn j a j N i a i N i1 β 算符优先分析算法 k:=1; S[k]:= # ; do{ 把下一个输入符号读进 a 中 ; if S[k] V ) j:=k else j:=k-1; while S[j] a){ do{ Q:=S[j]; ifs[j-1] V ) j:=j-1 else j:=j-2 }whiles[j] Q) 把 S[j1] S[k] 归约为某个 N; k:=j1; S[k]:=N; } if S[j] a S[j] a){ k:=k1; S[k]:=a }else error); } whilea!= # ) 42

43 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 5.4 优先函数 θ V, 定义自然数函数 fθ) 和 gθ), 使得 : 若 θ 1 θ 2, 则 fθ 1 ) < gθ 2 ) 若 θ 1 θ 2, 则 fθ 1 ) = gθ 2 ) 若 θ 1 θ 2, 则 fθ 1 ) > gθ 2 ) 那么,f 称为入栈优先函数,g 称为比较优先函数使用优先函数替代优先关系表的优点 : 优 : 便于比较运算 ; 节省存储空间正确性问题优先函数的问题 if θ 1 θ 2,then fθ 1 ) < gθ 2 ) ; 反之不然存在性问题并非总能把表映射到优先函数唯一性问题 a b a b ga) gb) fa) = > fb) = = 若 f 和 g 是算符优先文法 G 的优先函数, 那么对于任意自然数 C,fC 和 gc 也是 G 的优先函数构造优先函数的方法已知优先关系表, 构造一个有向图 H=V,), foreach a V ){ 置 f a V; 置 g a V} 结点为终结符 a 对应的符号 f a 和 g a ; if a b) 置 f a, g b ) 画结点 f a 到结点 g b 一条弧 ; if a b) 置 g b, f a ) 画结点 g b 到结点 f a 一条弧 ; 定义优先函数 f 和 g, 令 fa) 为从 f a 出发所能达到的结点个数 1; 令 ga) 为从 g a 出发所能达到的结点个数 1; 检查 f 和 g 有无矛盾, 若有则不存在优先函数否则成功例. 优先关系表 *F F F P^F P P ) i * ^ i ) # * ^ i ) # 43

44 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University g g * g^ g i g g ) g # g g * g^ g i g g ) g # f f f * f * f^ f^ f i f i f f f ) f # fx) gx) * ^ i ) # f ) f # * ^ i ) # fx) 6 gx) g g * g^ g i g g ) g # g g * g^ g i g g ) g # f f f * f * f^ f^ f i f i f f f ) f # * ^ i ) # fx) 6 8 gx) f ) f # * ^ i ) # fx) gx) 44

45 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University g g * g^ g i g g ) g # g g * g^ g i g g ) g # f f f * f * f^ f^ f i f i f f f ) f # * ^ i ) # fx) gx) f ) f # * ^ i ) # fx) gx) g g * g^ g i g g ) g # g g * g^ g i g g ) g # f f f * f * f^ f^ f i f i f f f ) f # * ^ i ) # fx) gx) f ) f # * ^ i ) # fx) gx) 45

46 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University g g * g^ g i g g ) g # g g * g^ g i g g ) g # f f f * f * f^ f^ f i f i f f f ) f # * ^ i ) # fx) gx) 5 7 f ) f # * ^ i ) # fx) gx) 结果验证 x * ^ i ) # fx) gx) if fθ 1 ) < gθ 2 )thenθ 1 θ 2 * ^ i ) # * ^ i ) # 优先函数构造方法的正确性若优先函数存在, 那么 : 若 a b 则 fa) = gb) 若 a b 则 fa) < gb) 若 a b 则 fa) > gb) 46

47 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 出错的情况 : 算符优先分析中的错误处理在归约最左素短语时无对应的产生式规则 ; 栈顶终结符与当前符号间无优先关系 ; 错误处理续 ) 错误 : 在归约最左素短语时无对应的产生式规则方法 : 寻找接近的候选式, 并根据情况报错若缺少终结符 a, 则 a 为非法符号若多出终结符 a, 则希望出现 a 错误处理续 ) 错误 : 在归约最左素短语时无对应的产生式规则可归约串 :N 1 b 1 N 2 b 2 N 3 N k b k N k1, 其中 b 1 b 2 b k 初始符号集 : {a V a b 1 } 结尾符号集 : {a V b k a } 方法 : 推断非终结符情况推断初始结尾符号集情况 i ) 缺举例两边不能够出现非终结符缺两边不能够出现非终结符 47

48 Yinliang Zhao 赵银亮 ) Xi an Jiaotong University 作业栈顶终结符与当前符号间无优先关系若 a c 则将 b 从栈顶移去若 b d 则将 c 删除找出 b e c 则把 e 插入输入串前端分析栈 b a 输入串 cd # P133 1, 51-3), 7, 8 上机题 B 编写程序输入一个算符优先文法, 自动构造出优先关系表并输出 ), 该程序还能对输入的句子进行语法分析, 依序输出分析过程中归约的最左素短语本题与上一章题目任选一个完成 ) 48

ebook14-4

ebook14-4 4 TINY LL(1) First F o l l o w t o p - d o w n 3 3. 3 backtracking parser predictive parser recursive-descent parsing L L ( 1 ) LL(1) parsing L L ( 1 ) L L ( 1 ) 1 L 2 L 1 L L ( k ) k L L ( 1 ) F i r s