The Implementations of Advanced LR Parser Algorithm

Transcript

1. RubyKaigi 2025 Ehime Prefectural Convention Hall 2025/04/17(Thu.) The Implementations of Advanced LR Parser Algorithm Junichi Kobayashi (@junk0612) ESM, Inc.
2. 自己紹介 Junichi Kobayashi • X / GitHub: @junk0612 • Working at ESM, Inc. ◦ Work as a Rails engineer ◦ A Member of Parser Club • Committer of Lrama • Hobbies ◦ Parsers ◦ Rhythm games ◦ Board games ◦ Haiku
5. Drinkup Sponsor
6. Ruby on Timeline
7. Attendee @nsgc Attendee @colorbox Attendees from ESM Attendee @S.H. Karaoke @fugakkbn Speaker @koic Attendee @wai-doi Speaker @junk0612 Attendee @kasumi8pon Attendee @mhirata Attendee @haruguchi Attendee @maimux2x
8. ✦ An LR parser generator built with Ruby Lrama
9. ✦ An algorithm of LR parser generation ✦ https://www.sciencedirect.com/science/article/pii/S0167 642309001191 IELR
10. ✦ https://github.com/ruby/lrama/pull/398 ✦ Support since Lrama 0.7 for CRuby 3.5 IELR in Lrama
11. Usage $ gem install lrama # from CLI $ lrama -D lr.type=ielr grammar.y # in grammar file %define lr.type ielr
12. ✦ Theoretical side ✦ Utilize the tokens read so far to narrow down the set of possible next tokens more accurately than LALR ✦ Practical side ✦ Propagating conflict info backward and lookahead forward ✦ Identify the conflict's cause and split states if necessary "After All, What is IELR?"
13. Theoretical Side Estimated: 5/30 min
14. ✦ Shift-Reduce Parsing ✦ One of Bottom-up Parsing ✦ Use 2 types of actions ✦ Shift: Get a next symbol from Lexer ✦ Reduce: Collapse recognized symbols into a parent node ✦ Use one of the actions depending on the situation ✦ Match one of grammar rules: Reduce ✦ Don't match any grammar rules: Shift Basis of LR Parser
15. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1
16. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1
17. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1
18. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num
19. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp
20. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp
21. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp
22. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num
23. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp
24. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp
25. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp
26. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp num
27. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp num exp
28. Behavior Example of LR Parser exp: exp + num | exp * num | num num: 0 | 1 1 + 0 * 1 num exp num exp num exp
29. Issue #1: Identifying Rule Matches
30. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
31. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
32. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
33. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
34. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
35. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
36. Motivating Examples method_call: method_name | method_name '(' args ')' save!(name: 'Junichi')
37. Issue #2: Collecting Next Tokens
38. ✦ Modifier conditional statements Motivating Examples statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')'
39. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
40. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
41. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
42. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
43. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
44. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
45. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
46. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
47. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
48. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
49. statement: method_call 'if' exp | method_call 'unless' exp method_call: method_name | method_name '(' args ')' save!(name: 'Junichi') save! if valid? save! end valid?
50. ✦ The next token is... ✦ included in same (or child) rule → Shift ✦ included in parent (or ancestors / sibling) rule → Reduce ✦ not included in both of the above → Error Select Actions
51. ✦ A set of tokens used to determine whether to Reduce ✦ LALR and IELR differ in how they compute their lookahead sets ✦ LALR: The set of all tokens that can appear immediately after a given nonterminal, based on the entire language ✦ IELR: The set of all tokens that can appear immediately after a given nonterminal, but only within the subset of language elements matching the tokens read so far Lookahead Set
52. ✦ conditional statements Motivating Examples cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')'
53. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
54. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
55. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
56. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
57. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
58. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
59. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
60. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
61. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
62. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
63. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
64. cond_stmt: 'if' method_call 'then' body 'end' | 'while' method_call 'do' body 'end' method_call: method_name | method_name '(' args ')' if valid? then save! end while valid? do save! end if valid? do save! end
65. ✦ original example in the paper Motivating Examples S: 'a' A 'a' | 'b' A 'b' A: 'a' | 'a' 'a' aaa / aaaa / bab / baab
66. ✦ original example Motivating Examples S: 'a' A 'a' | 'b' A 'b' A: 'a' | 'a' 'a' baab
67. ✦ original example Motivating Examples S: 'a' A 'a' | 'b' A 'b' A: 'a' | 'a' 'a' baab
68. ✦ A Conflict occurs when the parser can't uniquely decide the next action ✦ There are 2 types of Conflict ✦ Shift/Reduce Conflict ✦ Reduce/Reduce Conflict Conflicts
69. Practical Side Estimated: 15/30 min
70. LR Parser Model Parser State 0 State 1 State 2 State 3 NUM + exp State 4 State 5 State 6 * ( exp NUM - … Token Stream Source Code Lexer Grammar File Parser Generator 8 4 1 0
71. Shift Action 8 6 4 0
72. Shift Action 13 8 6 4 0
73. Reduce Action 13 8 6 4 0
74. Reduce Action 8 6 4 0
75. Reduce Action 6 4 0
76. Reduce Action 1 6 4 0
77. ✦ Can be parsed IELR but not LALR ✦ Caused by the difference of lookahead set ✦ May resolve by splitting states ✦ There are 3 types of Mysterious Conflicts ✦ Mysterious New Conflicts ✦ Mysterious Invasive Conflicts ✦ Mysterious Mutated Conflicts Mysterious Conflicts
78. Mysterious New Conflicts
79. Mysterious Invasive Conflicts
80. Mysterious Mutated Conflicts
81. Lrama's Implementation States State @states Transition Shift Goto Reduce @transitions @reduces @items @conflicts @id @next_sym @from_state @to_state @next_sym @from_state @to_state @look_ahead @item
82. ✦ Annotate conflicting states and their predecessors ✦ Recompute lookahead set from scratch ✦ Propagate it to next state ✦ Split the next state if the propagating lookahead set has no "compatibilities" with already propagated ones IELR Basic Idea
83. ✦ Indicates potential contribution to conflicts ✦ Has the following conflict information inside ✦ State ✦ Token ✦ Actions ✦ Items Inadequacy Annotations
84. Inadequacy Annotation
85. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
86. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
87. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
88. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
89. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
90. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
91. Inadequacy Annotation State: 22 Token: 'end' Actions: [S, R1, R2] Items: {R1 => [...], R2 => [...]} State: 27 Token: 'do' Actions: [R5, R6] Items: {R5 => [...], R6 => [...]}
92. 1. Lookahead sets: from its associated item's lookahead 2. Kernel lookahead: from the same item's lookahead in predecessor states (dot is one symbol to the left) 3. Non-kernel lookahead: from the follow set of the state's goto on the LHS (i.e., tokens that can appear next) 4. Goto follow set: a. the remainder of the RHS after the goto’s nonterminal b. The lookahead sets of items where the remainder is nullable Recompute Lookahead Set original: https://www.sciencedirect.com/science/article/pii/S0167642309001191 summarized by: @junk0612
93. Check Compatibilities S: 'a' A 'a' | 'b' A 'b' A: 'a' | 'a' 'a'
94. Check Compatibilities • A: 'a'・, ['a', 'b'] • A: 'a'・'a', ['a', 'b']
95. Check Compatibilities • A: 'a'・, ['a', 'b'] • A: 'a'・'a', ['a', 'b']
96. Check Compatibilities • A: 'a'・, ['a', 'b'] • A: 'a'・'a', ['a', 'b'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a
97. Check Compatibilities • A: 'a'・, ['a', 'b'] • A: 'a'・'a', ['a', 'b'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a
98. Check Compatibilities • A: 'a'・, ['a', 'b'] • A: 'a'・'a', ['a', 'b'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a Token: 'a' Actions: [S, R] Items: {R => [A: 'a'・]}
99. Check Compatibilities • A: 'a'・, ['a'] • A: 'a'・'a', ['a'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a Token: 'a' Actions: [S, R] Items: {R => [A: 'a'・]}
100. Check Compatibilities • A: 'a'・, ['a'] • A: 'a'・'a', ['a'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a Token: 'a' Actions: [S, R] Items: {R => [A: 'a'・]}
101. Check Compatibilities • A: 'a'・, ['b'] • A: 'a'・'a', ['b'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a Token: 'a' Actions: [S, R] Items: {R => [A: 'a'・]}
102. Check Compatibilities • A: 'a'・, ['b'] • A: 'a'・'a', ['b'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a Token: 'a' Actions: [S, R] Items: {R => [A: 'a'・]}
103. Check Compatibilities • A: 'a'・, ['a'] • A: 'a'・'a', ['a'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a • A: 'a'・, ['b'] • A: 'a'・'a', ['b']
104. Check Compatibilities • A: 'a'・, ['a'] • A: 'a'・'a', ['a'] • S: 'b'・A 'b', ['#'] • A:・'a', ['b'] • A:・'a' 'a', ['b'] • S: 'a'・A 'a', ['#'] • A:・'a', ['a'] • A:・'a' 'a', ['a'] a a • A: 'a'・, ['b'] • A: 'a'・'a', ['b'] No Conflicts!
105. $ bundle exec lrama -D lr.type=ielr parse.y
106. $ bundle exec lrama -D lr.type=ielr parse.y def compute_ielr (...snip...) rescue Interrupt end
107. ✦ Automaton has loops ✦ Compute lookahead sets slowly ✦ Create many "useless" annotations Why got stack
108. Looped Automatons
109. Looped Automatons
110. ✦ Introduce some caches ✦ Use strongly connected components algorithm ✦ Following the LALR Lookahead set computation Fasten Computation
111. Useless Annotations Actions: [R1, R2] Items: {R1 => [...], R2 => [...]}
112. Useless Annotations Actions: [R1, R2] Items: {R1 => [...], R2 => [...]} R1 R2
113. Useless Annotations Actions: [R1, R2] Items: {R1 => [...], R2 => [...]} R1 R2
114. $ time bundle exec lrama -D lr.type=ielr parse.y 69.02s user 0.29s system 99% cpu 1:09.38 total
115. Use IELR Parser in Ruby Estimated: 25/30 min
116. Generate IELR parser simply $ lrama --report=states parse.y $ mv parse.output lalr.output $ lrama --report=states -D lr.type=ielr parse.y $ mv parse.output ielr.output $ diff ielr.output lalr.output #=> no diffs!
117. ✦ There are 4 'do's in Ruby ✦ keyword_do ✦ keyword_do_cond ✦ keyword_do_block ✦ keyword_do_LAMBDA ✦ The tokens read so far provide sufficient information to decide Identify 4 'do's Smart obj.m(arg) do ... end while(true) do ... end obj.m arg do ... end -> (arg) do ... end
118. while obj.m do #=> keyword_do_cond while(obj.m do #=> keyword_do while(obj.m arg do #=> keyword_do_block while -> do #=> keyword_do_LAMBDA while obj.m -> do #=> keyword_do_LAMBDA while(obj.m -> do end do #=> keyword_do_block
119. ✦ Optimize IELR calculation ✦ Introduce IELR to CRuby and make parse.y better Future Work
120. ✦ @yui-knk, @ydah ✦ #LR_parser_gangs ✦ @koic, @S.H. ✦ #esm_parser_club ✦ My Wife ✦ #a_beautiful_life Acknowledgements
121. ✦ Theoretical side ✦ Utilize the tokens read so far to narrow down the set of possible next tokens more accurately than LALR ✦ Practical side ✦ Propagating conflict info backward and lookahead forward ✦ Identify the conflict's cause and split states if necessary "After All, What is IELR?"