Skip to content

Instantly share code, notes, and snippets.

@ydah
Created May 9, 2024 16:15
Show Gist options
  • Save ydah/62008655a6f6c3118ab01134dc91da6f to your computer and use it in GitHub Desktop.
Save ydah/62008655a6f6c3118ab01134dc91da6f to your computer and use it in GitHub Desktop.
Parameterizing rules meets conditional

Parameterizing rules meets conditional

Background

RubyのParserにおいて解決したい課題として、ParserとLexerが密結合していることが挙げられます。 その理由は様々ですが、一つの理由として特定の生成規則をある条件下では生成しないようにする必要がある場合があるからです。

たとえば、lambdaの仮引数には...を指定できないという例があります。

# good
-> (a) {}
-> (a=1) {}

# bad
-> (...) {} # syntax error

一方で生成規則を書く場合にはlambdaの引数であれ、メソッド定義の引数であれ、同じルールを使いたいという要求もあります。 parse.yではこのような要求を満たすために、lambdaの場合には...を受け付けないようにするために、tDOT3を返すようにしてSyntaxErrorを発生させています。 https://github.com/ruby/ruby/blob/444030fc6155d32c1f5211ba746bc9c76f70a96d/parse.y#L11250

これを実現するためには、生成規則に条件を付与する必要があります。 通常の生成規則に条件を付与するのは難しいですが、Parameterizing rulesによってパラメーターとして条件を受け取り展開する生成規則を制御することで実現できると考えました。

例えば、以下のブログに記載されているtDOT3のケース。 https://yui-knk.hatenablog.com/entry/2023/04/04/190413

f_argsはラムダ引数 (f_larglist) とメソッド定義引数 (f_arglist) の両方の生成規則の一部です。 RHSを辿っていくと f_args > args_tail > args_forward とtBDOT3は生成規則として有効なものなので、tDOT3を生成するためには今はLexerでtBDOT3を生成しているということです。

これは、要はある時にはtDOT3は有効な生成規則であるが、ある時には無効な生成規則であるということです。 つまり生成規則に条件を付与すれば解決できると考えています。

What

この提案では、生成規則に条件を付与するための構文を提案します。

%rule defined_rule(X, condition): /* empty */
                                | X { $$ = $1; } %if(condition) /* 1 */
                                | %if(condition) X %endif X { $$ = $1; } /* 2 */
                                ;

%%

r_true        : defined_rule(number, %true)
              ;

r_false       : defined_rule(number, %false)
              ;

これは、defined_ruleという生成規則にconditionという条件のパラメーターを付与する構文です。 条件のtrue/falseの指定の場合には%true%falseというキーワードを使います。

/* 1 / は、Rubyでいうところの後置ifのような構文です。conditionがfalseの場合には該当する行の生成規則は展開されません。 / 2 */ は、通常のif文のような構文です。conditionがfalseの場合には%if%endifの間の生成規則は展開されません。

つまり、上記の例では以下の通り展開されます。

❯ exe/lrama --trace=rules spec/fixtures/parameterizing_rules/user_defined/if.y
Grammar rules:
$accept -> r_true YYEOF
defined_rule_number_true -> ε
defined_rule_number_true -> number
defined_rule_number_true -> number number
r_true -> defined_rule_number_true
defined_rule_number_false -> ε
defined_rule_number_false -> number
r_false -> defined_rule_number_false

Details

条件の指定について、%true%falseとしているのは、symbol名としてのtruefalseを予約語として使うのは避けたいためです。 多くの場合の他のキーワードも同様に%を付与しているので、このような形式にしました。

rule_builderでのParameterizing rulesの展開の部分で実装を行います。 RHSの展開の際に、%if%endifの間の生成規則を展開するかどうかを判定する部分と、後置の%ifがある場合には、その行のすべての生成規則を展開するかどうかを判定する部分を追加します。

必要な条件についてはあと追加するとしても%elseのみになると考えています。 elsifのような構文は基本的には%true%falseを渡すこの機能の性質上、必要ないと考えています。

また、この機能を実装するにあたって新たにバリデーションを追加する必要があると考えています。 具体的には%ifが定義されていないが%endifが定義されている場合や、%ifが定義されているが%endifが定義されていない場合などが考えられるためです。 考えられるのは以下のようなバリデーションです。

  • %ifが定義されていないが%endifが定義されている場合
  • %ifが定義されているが対応する%endifが定義されていない場合

Proof of concept

ruby/lrama#418

References

https://yui-knk.hatenablog.com/entry/2023/04/04/190413

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment