Share
Embed
LRパーサーはいいぞ
Kernel/VM探検隊@関西 11回目「LRパーサーはいいぞ」の発表スライド
https://kernelvm.connpass.com/event/347564/
ydah
May 11, 2025
Transcript
54 slides
-
1BSTFSͱ-FYFS ࣈ ۟ ղ ੳ ث ߏ จ ղ ੳ
ث จࣈྻ όΠτྻ τʔΫϯྻ நߏจ "45 -
1BSTFSͱ-FYFS ࣈ ۟ ղ ੳ ث ߏ จ ղ ੳ
ث จࣈྻ όΠτྻ τʔΫϯྻ நߏจ "45 -
-FYFS ॲཧܥ͔ΒݟΔͱόΠτྻ จࣈͷฒͼΛղੳ͠ɺҙຯͷ͋Δ࠷খͷ୯ҐʢτʔΫϯʣʹղ͢Δ 64 65 66 20 6d 65 74
68 6f 64 5f 6e 61 6d 65 28 70 61 72 61 6d 29 0a 20 20 70 75 74 73 20 70 61 72 61 6d 0a 65 6e 64 def method_name param -
1BSTFSͱ-FYFS ࣈ ۟ ղ ੳ ث ߏ จ ղ ੳ
ث จࣈྻ όΠτྻ τʔΫϯྻ நߏจ "45 -
1BSTFS τʔΫϯྻ͕จ๏తʹਖ਼͍͔͠Λݕࠪͯ͠நߏจ "45 Λ࡞͢Δ def method_name(param) puts param end defn
ar g s body fcall puts ar g s '(' keyword_def tIDENTIFIER tIDENTIFIER ')' ... -
จ๏ϑΝΠϧ #/' #BDLVTr/BVS'PSN Ͱจ๏Λهड़͢Δ #/'ͱจ๏نଇΛఆٛ͢ΔͨΊͷه๏ͰɺਓؒʹͱͬͯײతͰཧղ͍͢͠ expr : NUMBER { $$
= $1; } | expr '+' expr { $$ = $1 + $3; } ; -
1BSTFS(FOFSBUPS ΞʔΩςΫνϟ $PNNBOE -JOF *OUFSGBDF จ๏ϑΝΠϧ 1BSTFS (SBNNBS 4ZTUFN 4UBUF
.BOBHFS $PEF (FOFSBUPS -
1BSTFS(FOFSBUPS ΞʔΩςΫνϟ $PNNBOE -JOF *OUFSGBDF จ๏ϑΝΠϧ 1BSTFS (SBNNBS 4ZTUFN 4UBUF
.BOBHFS $PEF (FOFSBUPS -
$PNNBOE-JOF*OUFSGBDF -SBNBͷίϚϯυ࣮ߦΛ࢘Δத৺తͳΫϥε ೖྗͱͳΔจ๏ϑΝΠϧ֤छΦϓγϣϯΛड͚औͬͯɺ1BSTFSੜϓϩ ηεશମͷΦʔέετϨʔγϣϯΛߦ͏ % lrama - h Lrama is
LALR (1) parser generator written by Ruby. Usage: lrama [options] FILE STDIN mode: lrama [options] - FILE read grammar from STDIN Tuning the Parser: -S, - - skeleton=FILE specify the skeleton to use - t, - - debug display debugging outputs of internal parser same as '-Dparse.trace' - - locations enable location support -D, - - def i ne=NAME[=VALUE] similar to '%def i ne NAME VALUE' -
1BSTFS(FOFSBUPS ΞʔΩςΫνϟ $PNNBOE -JOF *OUFSGBDF จ๏ϑΝΠϧ 1BSTFS (SBNNBS 4ZTUFN 4UBUF
.BOBHFS $PEF (FOFSBUPS -
SBDDͰ#JTPOΛஔ͖͑Ε͍͍ͷͰ ੜΞϧΰϦζϜಉ͡Ͱ-"-3 ೖྗͷจ๏ϑΝΠϧͦͷͷͷจ๏ϑΝΠϧ͕ҟͳΔ #JTPO:BDD#JTPOܗࣜɺSBDDಠࣗͷه๏ ग़ྗ͢Δ1BSTFSͷݴޠ͕ҟͳΔ #JTJPO$ݴޠɺSBDD3VCZ parser_option: "%expect"
INTEGER { @grammar.expect = val[1] } | "%def i ne" variable value { @grammar.def i ne[val[1].s_value] = val[2]&.s_value } -
(SBNNBS4ZTUFN "DUJPOTͷ෦ͷղੳࢀরղܾඞཁ "DUJPOจ๏نଇʹҰகͯؐ͠ݩ͢Δॠؒʹ࣮ߦ͞ΕΔ ɺOɺ!Oͱ͍͏ಛघͳมΛ༻͢Δ͜ͱͰऴɾඇऴه߸ͷ ҐஔใʹΞΫηεՄೳͳͷͰɺͦΕΒΛஔ͖͑Δ if_tail: opt_else | k_elsif expr_value
then compstmt(stmts) if_tail { $$ = new_if(p, $2, $4, $5, &@$, &@1, &@3, &NULL_LOC); f i xpos($$, $2); / * % ripper: elsif!($ : 2, $ : 4, $ : 5) % * / } ; -
1BSTFS(FOFSBUPS ΞʔΩςΫνϟ $PNNBOE -JOF *OUFSGBDF จ๏ϑΝΠϧ 1BSTFS (SBNNBS 4ZTUFN 4UBUF
.BOBHFS $PEF (FOFSBUPS -
1BSTFS(FOFSBUPS ΞʔΩςΫνϟ $PNNBOE -JOF *OUFSGBDF จ๏ϑΝΠϧ 1BSTFS (SBNNBS 4ZTUFN 4UBUF
.BOBHFS $PEF (FOFSBUPS -
$PEF(FOFSBUPS εςʔτϚγϯͱߏจղੳදΛݩʹ࣮ߦՄೳͳ1BSTFSͷίʔυΛੜ͢Δ 5FNQMBUFʹΛຒΊࠐΜͰ͍͘ SVCZFSCͱ͍͏ςϯϓϨʔτγεςϜΛͬͯຒΊࠐΉ / * - - - -
- - - - - - . | yyparse. | ` - - - - - - - - - - * / int yyparse (<%= output.parse_param %>) { <%# b4_declare_scanner_communication_variables -%> / * Lookahead token kind. * / int yychar; / * The semantic value of the lookahead symbol. * / / * Default value used for initialization, for pacifying older GCCs or non-GCC compilers. * / #ifdef _ _ cplusplus static const YYSTYPE yyval_default = {}; (void) yyval_default; #else YY_INITIAL_VALUE (static const YYSTYPE yyval_default;) -
1BSBNFUFSJ[JOH3VMFT 0$BNM͚ͷ-3 QBSTFSHFOFSBUPSͰ͋Δ.FOIJSͷศརػೳ ੜنଇͷඇऴه߸ͷఆٛʹ͓͚Δڞ௨తͳύλʔϯΛநԽ͢ΔͨΊ ͷจ๏Λఏڙ͢Δ Πϝʔδͱͯ͠ϝιουͱͯ͠நग़Ͱ͖ΔΑ͏ʹ͢ΔͨΊͷػೳ .FOIJS3FGFSFODF.BOVBM WFSTJPO
IUUQTHBMMJVNJOSJBGSdGQPUUJFSNFOIJSNBOVBMIUNMTFD -
ࣅͨΑ͏ͳߏΑ͋͘Δ stmt : keyword_alias f i tem . . .
| lhs '=' lex_ctxt mrhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } command_asgn : lhs '=' lex_ctxt command_rhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } arg : lhs '=' lex_ctxt arg_rhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } -
ࣅͨΑ͏ͳߏΑ͋͘Δ stmt : keyword_alias f i tem . . .
| lhs '=' lex_ctxt mrhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } command_asgn : lhs '=' lex_ctxt command_rhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } arg : lhs '=' lex_ctxt arg_rhs { $$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } -
ߏΛநग़͢Δ͜ͱ͕Ͱ͖Δ %rule asgn(rhs) <node> : lhs '=' lex_ctxt rhs {
$$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } ; stmt : keyword_alias f i tem . . . | asgn(rhs) ; arg : asgn(arg_rhs) ; command_asgn : asgn(command_rhs) ; -
ύϥϝʔλͱͯ͠5PLFOΛ͢͜ͱ͕Ͱ͖Δ %rule asgn(rhs) <node> : lhs '=' lex_ctxt rhs {
$$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } ; stmt : keyword_alias f i tem . . . | asgn(rhs) ; arg : asgn(arg_rhs) ; command_asgn : asgn(command_rhs) ; -
͞Εͨ5PLFOΛӈลʹల։͢Δ %rule asgn(rhs) <node> : lhs '=' lex_ctxt rhs {
$$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } ; stmt : keyword_alias f i tem . . . | asgn(rhs) ; arg : asgn(arg_rhs) ; command_asgn : asgn(command_rhs) ; -
͞Εͨ5PLFOΛӈลʹల։͢Δ %rule asgn(rhs) <node> : lhs '=' lex_ctxt rhsarg_rhs {
$$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } ; stmt : keyword_alias f i tem . . . | asgn(rhs) ; arg : asgn(arg_rhs) ; command_asgn : asgn(command_rhs) ; -
͞Εͨ5PLFOΛӈลʹల։͢Δ %rule asgn(rhs) <node> : lhs '=' lex_ctxt rhscommand_rhs {
$$ = node_assign(p, $1, $4, $3, &@$); / * % ripper: assign!($ : 1, $ : 4) % * / } ; stmt : keyword_alias f i tem . . . | asgn(rhs) ; arg : asgn(arg_rhs) ; command_asgn : asgn(command_rhs) ; -
จ๏ͷߏΛ͍͍ײ͡ʹݟ͍ͨ brace_block : '{' brace_body '}' { $$ = $2;
set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } | k_do do_body k_end { $$ = $2; set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } ; -
จ๏ͷߏͱ"DUJPO͕ࠞࡏ brace_block : '{' brace_body '}' { $$ = $2;
set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } | k_do do_body k_end { $$ = $2; set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } ; -
จ๏ͷߏͱ"DUJPO͕ࠞࡏ brace_block : '{' brace_body '}' { $$ = $2;
set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } | k_do do_body k_end { $$ = $2; set_embraced_location($$, &@1, &@3); / * % ripper: $ : 2 % * / } ;