$30 off During Our Annual Pro Sale. View Details »

How does Lrama make the Ruby parser grammar G.O...

ydah
September 13, 2024

How does Lrama make the Ruby parser grammar G.O.A.T.?

EuRuKo 2024「How does Lrama make the Ruby parser grammar G.O.A.T.?」の発表スライド。
#EuRuKo2024 #EuRuKo https://2024.euruko.org/speakers/yudai_takada

Reference:
Lrama LALR (1) parser generator https://github.com/ruby/lrama
Menhir Reference Manual(version 20231231) https://gallium.inria.fr/~fpottier/menhir/manual.html
Language and Grammar (Bison 3.8.1) https://www.gnu.org/software/bison/manual/html_node/Language-and-Grammar.html
Chomsky hierarchy - Wikipedia https://en.wikipedia.org/wiki/Chomsky_hierarchy
Named References (Bison 3.8.1) https://www.gnu.org/software/bison/manual/html_node/Named-References.html
Ruby Parser Roadmap - Google slide https://docs.google.com/presentation/d/1E4v9WPHBLjtvkN7QqulHPGJzKkwIweVfcaMsIQ984_Q/edit#slide=id.p

ydah

September 13, 2024
Tweet

More Decks by ydah

Other Decks in Technology

Transcript

  1. How does Lrama make the Ruby parser grammar G.O.A.T.? EuRuKo

    2024—Sarajevo, Bosnia & Herzegovina Hotel Hills: Congress & Thermal Spa Resort 13 September 2024 Yudai Takada (@ydah)
  2. RubyKaigi RubyKaigi is an international conference on the Ruby programming

    language in Japan. 8FMPPLGPSXBSEUPZPVSBUUFOEBODF
  3. Confidential “It is hard, if not possible, to build a

    robust compiler out of "hacks."” — Ravi Sethi Beginning of the journey ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  4. • LALR (1) parser generator written by Ruby • Output

    a LALR parser written by C with “parse.y” as input • Replace GNU Bison with Lrama in Ruby 3.3.0 ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ What is Lrama? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  5. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Why use Lrama instead of Bison? •

    We can move away from supporting multiple versions • Its easy to add new functions and grammar. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  6. ^^ LALR (1) parser generator ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah |

    https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  7. LA LR (1) parser ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Look-Ahead Left-to-right Rightmost

    derivation Number of tokens to Look-Ahead ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  8. • Lrama is a Pure Ruby LALR parser generator •

    In Ruby 3.3.0 replaces GNU Bison with Lrama • LALR (1) parser refers to a Lookahead Left-to- Right, Rightmost derivation parser. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Summary ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  9. “Computers are good at following instructions, but not at reading

    your mind.” — Donald E. Knuth Components Related to Parsing ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  10. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Lexer Parser Compiler Text Tokens AST ISeq

    ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  11. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Lexer Parser Compiler Text Tokens AST ISeq

    ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  12. • Converts source code into tokens, the building blocks for

    further compilation ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Lexer, Lexical analysis ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  13. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ def method_name(pa r am) puts pa r

    am end Lexer, Lexical analysis ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  14. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ def method_name(pa r am) puts pa r

    am end Lexer, Lexical analysis def method_name ( param ) ... ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  15. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Lexer Parser Compiler Text Tokens AST ISeq

    ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  16. • Check the Lexer output token for grammatical conformance and

    create an AST • Appropriate error handling is done for grammatically incorrect programs ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Parser ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  17. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ def method_name(pa r am) puts pa r

    am end Parser def method_name ( param ) ... defn args body fcall puts args ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  18. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ❯ r uby - - dump=pa r

    set r ee - e 'p "EuRuKo"' : (snip) # @ NODE_SCOPE (id: 3, line: 1, location: (1,0)-(1,10)) # +- nd_tbl: (empty) # +- nd_a r gs: # | (null node) # +- nd_body: # @ NODE_FCALL (id: 0, line: 1, location: (1,0)-(1,10))* # +- nd_mid: :p # +- nd_a r gs: # @ NODE_LIST (id: 2, line: 1, location: (1,2)-(1,10)) # +- nd_alen: 1 # +- nd_head: # | @ NODE_STR (id: 1, line: 1, location: (1,2)-(1,10)) # | +- nd_lit: "EuRuKo" # +- nd_next: # (null node) Parser ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  19. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Lexer Parser Compiler Text Tokens AST ISeq

    ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  20. • Ruby compiles into machine language for virtual machines(YARV), and

    then the virtual machines execute ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Compiler ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  21. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ i r b(main) : 001> iseq =

    RubyVM : : Inst r uctionSequence.compile("p 'EuRuKo'") i r b(main) : 002> puts iseq.disasm = = disasm: #<ISeq : < compiled>@<compiled > : 1 (1,0)-(1,10)> 0000 putself ( 1)[Li] 0001 putst r ing "EuRuKo" 0003 opt_send_without_block <calldata!mid:p, a r gc:1, FCALL|ARGS_SIMPLE> 0005 leave Compiler ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  22. • Generates a parser from a formal grammar speci fi

    cation • Takes a set of rules de fi ning the syntax of a programming language or data format and produces code that can parse strings according to those rules ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Parser Genarator ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  23. • Components related to parsing are lexer, parser and compiler

    • Parser generater generates a parser from a set of rules de fi ning the syntax of a programming language or data format ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Summary ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  24. “The only languages which do not change are dead ones.”

    — David Crystal What is parser grammar? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  25. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Recursively eunmrable Context-sensitive Context-free Regular Turing machine

    Linear-bounded non-deterministic Turing machine non-deterministic pushdown auto-maton fi nite-state automaton Chomsky hierarchy ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  26. In order for Bison to parse a language, it must

    be described by a context-free grammar. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ In Bison https://www.gnu.org/software/bison/manual/html_node/Language-and-Grammar.html ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  27. • BNF (Backus-Naur form) is a notation for expressing Context-free

    grammar • Standard format for describing context-free grammars and is used to de fi ne the syntax of programming languages and protocols ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Notation for representing CFG ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  28. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  29. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; LHS (Left Hand Side) RHS (Right Hand Side) ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  30. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; Nonterminal Symbol Terminal Symbol ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  31. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; (Semantic) Actions ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  32. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; Numbered Parameter Numbered Parameter ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  33. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; Refers to the value of the token ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  34. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ BNF expr : NUMBER { $$ =

    $1; } | expr '+' expr { $$ = $1 + $3; } ; Behaves like a return value ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  35. • Includes Grammar Rules, Actions, Token De fi nitions and

    Error Handling • Like a blueprint that tells Ruby how to understand and execute programs by breaking down code into its fundamental components and rules ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ parse.y ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  36. • LR parsers can parse Context-free grammar • Context-free grammar

    can be expressed using Backus-Naur form • Ruby uses BNF in a fi le called parse.y to de fi ne Ruby grammar and behavior ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Summary ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  37. “The best programs are written so that computing machines can

    perform them quickly and so that human beings can understand them clearly.” — Donald E. Knuth How does Lrama make the Ruby parser grammar G.O.A.T.? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  38. • Maintainability • “parse.y” is dif fi cult • Be

    likened to a Demon Castle, Hell and Monstrous • What's the dif fi culty? • Grammar provided by Bison is primitive ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ What is issue? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  39. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ expr : NUMBER { $$ = $1;

    } | expr '+' expr { $$ = $1 + $3; } ; Numbered Parameters ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  40. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ lambda : tLAMBDA { : (snip) }<va

    r s> max_numpa r am numpa r am it_id allow_exits f_la r glist { : (snip) } lambda_body { $$ = NEW_LAMBDA($5, $7, &loc); } ; Numbered Parameters Which are the 5th and 7th tokens? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  41. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ lambda : tLAMBDA { : (snip) }<va

    r s> max_numpa r am numpa r am it_id allow_exits f_la r glist < - - - - - - 5th { : (snip) } lambda_body < - - - - - 7th { $$ = NEW_LAMBDA($5, $7, &loc); } ; Numbered Parameters ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  42. • This is a Bison's feature • Original symbol names

    may be used as named reference • Enclosing with [] in rule descriptions allows for assigning alias name for reference ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Named References ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  43. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ expr : NUMBER { $$ = $1;

    } | expr '+' expr { $$ = $1 + $3; } ; befo r e ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  44. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ expr[result] : NUMBER { $result = $NUMBER;

    } | expr[left] '+' expr[right] { $result = $left + $right; } ; Afte r ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  45. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ expr[result] : NUMBER { $result = $NUMBER;

    } | expr[left] '+' expr[right] { $result = $left + $right; } ; Refer to the NUMBER on the RHS ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  46. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ expr[result] : NUMBER { $result = $NUMBER;

    } | expr[left] '+' expr[right] { $result = $left + $right; } ; De fi ne Alias Use Alias Use Alias De fi ne Alias ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  47. What if there are duplicate code or logic? ydah |

    https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  48. 🧐 Modularization: Break down systems into reusable components (e.g., methods,

    modules, classes) to avoid duplication. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  49. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ f_kwa r g : f_kw { $$

    = $1; / * % r ippe r : r b_a r y_new3(1, get_value($ : 1)) % * / } | f_kwa r g ',' f_kw { $$ = kwd_append($1, $3); / * % r ippe r : r b_a r y_push(get_value($ : 1), get_value($ : 3)) % * / } ; def foo(ba r :, baz:) end ^^^^^^^^^^^^^ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  50. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ f_block_kwa r g: f_block_kw { $$ =

    $1; / * % r ippe r : r b_a r y_new3(1, get_value($ : 1)) % * / } | f_block_kwa r g ',' f_block_kw { $$ = kwd_append($1, $3); / * % r ippe r : r b_a r y_push(get_value($ : 1), get_value($ : 3)) % * / } ; foo { |ba r :, baz:| puts " # { ba r }- # { baz}" } ^^^^^^^^^^^^^ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  51. • The de fi nition of a Nonterminal symbol can

    be parameterized with other (Terminal or Nonterminal) symbols • Idea of Parameterizing Rules comes from Menhir LR(1) parser generator • https://gallium.inria.fr/~fpottier/menhir/manual.html#sec32 parser generator ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Parameterizing Rules ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  52. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ f_kwa r g : f_kw { $$

    = $1; / * % r ippe r : r b_a r y_new3(1, get_value($ : 1)) % * / } | f_kwa r g ',' f_kw { $$ = kwd_append($1, $3); / * % r ippe r : r b_a r y_push(get_value($ : 1), get_value($ : 3)) % * / } ; f_block_kwa r g: f_block_kw { $$ = $1; / * % r ippe r : r b_a r y_new3(1, get_value($ : 1)) % * / } | f_block_kwa r g ',' f_block_kw { $$ = kwd_append($1, $3); / * % r ippe r : r b_a r y_push(get_value($ : 1), get_value($ : 3)) % * / } ; befo r e ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  53. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules kwa r g(kw) :

    kw { $$ = $1; / * % r ippe r : r b_a r y_new3(1, get_value($ : 1)) % * / } | kwa r g(kw) ',' kw { $$ = kwd_append($1, $3); / * % r ippe r : r b_a r y_push(get_value($ : 1), get_value($ : 3)) % * / } ; f_kwa r g : kwa r g(f_kw); f_block_kwa r g : kwa r g(f_block_kw); afte r ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  54. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules option(X) : / *

    empty * / | X ; Rule name Parameter Parameter is expanded here ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  55. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ opt_nl : / * empty * /

    | '\n' ; ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  56. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules option(X) : / *

    empty * / | X ; opt_nl : option('\n') ; ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  57. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules option('\n') : / *

    empty * / | X ; opt_nl : option('\n') ; ^^^^^^ Be expanded ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  58. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules option('\n') : / *

    empty * / | '\n' ; opt_nl : option('\n') ; ^^^^^^ ^^^^^^ Be expanded Be expanded ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  59. • Provides a Standard Library of rules with a general

    structure, such as `option` or `list` • Stored in a fi le lib/lrama/grammar/stdlib.y, which is embedded inside grammar fi le when before parsing ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Standard library ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  60. The following three rules can be created using the familiar

    regular expression-like syntax: ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Standard library Names Recognizes Alias option(X) є | X X? list(X) a possibly empty sequence of X’s X* nonempty_list(X) a nonempty sequence of X’s X+ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  61. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ % r ules option(X) : / *

    empty * / | X ; opt_nl : option('\n') ; befo r e ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  62. ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ opt_nl : '\n'? ; afte r ydah

    | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  63. Ruby parser's grammar is now G.O.A.T., right? ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ

    ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  64. • Currently, with the replacement of the parser generator from

    Bison to Lrama, we have more powerful and richer grammars • Named References solved the problem of easily hard-to-read references • Parameterizing Rules gave us a great power to abstract structures • The syntax continues to evolve and the G.O.A.T. continues to be updated on a daily basis ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Summary ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  65. “People think that computer science is the art of geniuses

    but the actual reality is the opposite, just many people doing things that build on eachother, like a wall of mini stones.” — Donald E. Knuth Conclusion ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  66. • One of the problems with parse.y was the issue

    of maintainability • It was suggested that just extending the grammar would bring signi fi cant improvements to the Ruby parser grammar • The syntax continues to evolve throughout the development of Lrama, and the G.O.A.T. continues to be updated daily ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Conclusion ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ
  67. • Lrama LALR (1) parser generator https://github.com/ruby/lrama • Menhir Reference

    Manual(version 20231231) https://gallium.inria.fr/~fpottier/menhir/manual.html • Language and Grammar (Bison 3.8.1) https://www.gnu.org/software/bison/manual/html_node/ Language-and-Grammar.html • Chomsky hierarchy - Wikipedia https://en.wikipedia.org/wiki/Chomsky_hierarchy • Named References (Bison 3.8.1) https://www.gnu.org/software/bison/manual/html_node/Named- References.html • Ruby Parser Roadmap - Google slide https://docs.google.com/presentation/d/ 1E4v9WPHBLjtvkN7QqulHPGJzKkwIweVfcaMsIQ984_Q/edit#slide=id.p ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ Reference ydah | https://speakerdeck.com/ydah/how-does-lrama-make-the-ruby-parser-grammar-goatɹɹ