rakulang, dartlang, nimlang, golang, rustlang, lang lang no see

从正则表达式到 Grammar(第二部分)

焉知非鱼

From Regex to Grammar

如果你是正则表达式新人(至少当它们用于 Raku 中时), 那我建议你从这个系列的第一部分开始。那些掌握了一定正则表达式的人可以跳过上周的文章。现在, 继续演示!

上周轶事 #

我们开始开发一个接收诸如:

var a = 3; console.log("Hey, did you konw a = " + a + "?");

Javascript 表达式的 Raku 编译器, 并把这段代码转换为 Rakudo 那样的编译器能运行的 Raku 代码。在我们开始之前, 想想转换后的 Raku 代码看起来是什么样的可能会是个好主意。如果你已经知道了 Perl 5, 那么你应该熟悉这样的代码。

my $a = 3;
say "Hey, did you konw a = " ~ $a ~ "?";

我们将需要确保我们的正则表达式捕获到了 Javascript 的要素。如果你还记得上一次, 我们使用这样一组正则表达式来捕获我们的文本:

my rule Number                { \d+                                                          };
my rule Variable              { \w+                                                          };
my rule String                { '"' <-[" ]>+ '"'                                             };
my rule Assignment-Expression { var <Variable> '=' <Number>                                  };
my rule Function-Call         { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };

say 'var a = 3; console.log("Hey, did you konw a = " + a + "?");' ~~ rule { <Assignment-Expression> ';'  <Function-Call> ';' };

如果你把这段代码放到一个 Raku 源文件中并运行它, 那么它的输出第一次看起来可能会有点奇怪:

「var a = 3; console.log( "Hey, did you know a = " + a + "?" );」
 Assignment-Expression => 「var a = 3」
    Variable => 「a 」
    Number => 「3」
 Function-Call => 「console.log( "Hey, did you know a = " + a + "?" )」
    String => 「"Hey, did you know a = " 」
    Variable => 「a 」
    String => 「"?" 」

如果你愿意暂时忽略 「」 标记, 你会看到匹配被缩进了, 几乎像资源管理器窗口一样, <Assignment-Expression> 作为目录, VariableNumber 作为目录里面的文件。实际上, 那离真相不远了。当我看到这种结构时, 我发现使用一点添加的语法能帮助我们像这样来观察它:

$/ => 「var a = 3; console.log( "Hey, did you know a = " + a + "?" );」
 <Assignment-Expression> => 「var a = 3」
    <Variable> => 「a 」
    <Number> => 「3」
 <Function-Call> => 「console.log( "Hey, did you know a = " + a + "?" )」
    <String> => 「"Hey, did you know a = " 」
    <Variable> => 「a 」
    <String> => 「"?" 」

这几乎让怎么打印出文本变得更容易, 并在我们的正则表达式中指出了一个小问题。我们来打印给变量 a 所赋的数字, 从这儿开始。第一行告诉我们目录的根, 或者匹配树是 $/。如果你在测试文件的末尾添加上 say $/; 并返回它, 那么你会看到整个表达式被打印出了 2 次。那一定意味着 $/ 就是整个匹配。

每向下推进一层就是把 => 箭头的左侧的东西添加到 $/ 的右边。把之前的 say 语句修改为 say $/<Assignment-Expression>;, 并看看输出发生了什么改变。它现在看起来应该像这样:

「var a = 3」
  Variable => 「a 」
  Number => 「3」

让我们把把标记(不可见)添加进来, 所以我们能知道到了哪里…

$/<Assignment-Expression> => 「var a = 3」
  <Variable> => 「a 」
  <Number> => 「3」

我们现在能看到我们的目标, 数字 3, 仅仅实在更下面的一层。和上次一样, 我们能够添加表达式左侧的东西, 所以我们就动手吧。

say $/<Assignment-Expression><Number>;
  3

我们几乎得到我们想要的了。「」 挡道, 所以我们在这儿把值转换回数字。我把转换(cast)用引号扩起来, 因为它不是 C/C++ 程序员那样认为的"casting"。我们想做的大约等价于 sscanf(str,"%d",&num), 但是在 Raku 中, 这个操作符更加简单:

say +$/<Assignment-Expression><Number>; # 3

如果不深入更多细节, 那么 $/ 是一个里面藏着隐式数字、字符串和布尔值的对象。前面添加的 + 把隐藏在 $/ 对象中的数字显示出来了。

从 Javascript 到 Perl #

我们离从 Javascript 生成 Raku 代码不远了。让我们使用上面所学的开始我们的第一个语句, 赋值语句。

say 'my $' ~ $/<Assignment-Expression><Variable> ~ ' = ' ~
      $/<Assignment-Expression><Number> ~ ';';

my $a = 3;

我们仅仅使用了 7 行 Raku 就把代码从一种语言转换为另外一种语言。并且大部分的 Raku 代码都是可重用的, 因为字符串, 数字, 和 Javascript/C/Java 风格的变量名在大部分语言之间是通用的。

上次, 我们学习了怎么使用正则表达式来创建匹配。这次我们学会了怎么使用我们说匹配到的东西, 还有怎么在 say 语句中找出我们想要的东西。 不可见的匹配标记相当有用, 我可能会写一个模块来把它们放回到匹配表达式中, 那应该不难。

那个方案有一个问题, 如果我们看一下 <Function-Call> 匹配, 会很容易发现那个问题。

$/<Function-Call> => console.log( "Hey, did you know a = " + a + "?" )
  <String> => "Hey, did you know a = " 
  <Variable> => a 
  <String> => "?" 

当我们写了 say $/<Function-Call><String>; 时, 我们会获取哪个 <String>? 在你运行这段代码之前, 先猜测一下。会是第一个吗, 因为一旦匹配对象被创建, Raku 就不会把它替换掉? 会是最后一个吗, 因为最后一个"覆盖"了第一个? 编译器会仅仅"感到困惑"然后什么也不打印吗? 运行一下看看!

它实际上以一个列表的形式把两个匹配都返回了, 所以你可以引用任何一个。 我们的不可见标记现在看起来长这样:

$/<Function-Call> => 「console.log( "Hey, did you know a = " + a + "?" )」
  <String>[0] => 「"Hey, did you know a = " 」
  <Variable> => 「a 」
  <String>[1] => 「"?" 」

所以, 如果我们想打印第一个字符串, 我们可以写上 say $/<Function-Call><String>[0]; 并得到含有时髦的日语标记的「“Hey, did you know a = " 」。幸运的是有一种便捷方式来避免那些日语标记, 就像数字 3 中的那样:

say ~$/<Function-Call><String>[0];
 "Hey, did you know a = "

~ 操作符使匹配字符串化, 就像 + 让返回的匹配数字化一样。所以你可能自己把最后一行写作:

say 'say ' ~ $/<Function-Call><String>[0] ~ ' ~ '
  ' $' ~ $/<Function-Call><Variable> ~ ' ~ '
  $<Function-Call><String>[1] ~ ';';

say "Hey, did you know a = " ~ $a ~ "?";

我们已经把我们的两行 Javascript 代码编译成 Raku 代码了。

重构 #

现在已经能工作了, 但是有很多重复。目前我们得到是:

my rule Variable               { \w+                                                          };
my rule String                 { '"' <-[ " ]>+ '"'                                            };
my rule Assignment-Expression  { var <Variable> '=' <Number>                                  };
my rule Function-Call          { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };

'var a = 3; console.log( "Hey, did you know a = " + a + "?" );' ~~ rule { <Assignment-Expression> ';' <Function-Call> ';' }

say 'my $' ~ $/<Assignment-Expression><Variable> ~ ' = ' ~ $/<Assignment-Expression><Number> ~ ';';
say 'say ' ~ $/<Function-Call><String>[0] ~ ' ~ $' ~ $/<Function-Call><Variable> ~  ' ~ ' ~ $/<Function-Call><String>[1] ~  ';';

那些 rules 看起来相当好, <String><Variable> 的重复也是不可避免的。 但是看看 say 语句, 你会看到 <Assignment-Expression><Function-Call> 重复了自身好几次。避免这种重复的一种方法是创建一个临时变量, 但是那可能会变得丑陋。

my $assignment-expression = $/<Assignment-Expression>;
say 'my $' ~ $assignment-expression<Variable> ~ ' = ' ~  $assignment-expression<Number> ~ ';'

相反, 我们利用 Raku 的子例程签名, 并且重用 $/ 变量名以使我们能重用上面所写的代码, 然后拿掉 <Assignment-Expression> 部分。 我会把子例程的名字命名为 rule 的名字, 只是为了直接了当。(你会在之后看到为什么这样做。)

sub  assignment-expression($/) {
    'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
}

say assignment-expression( $/<Assignment-Expression> );

让我们对 <Function-Call> 也做同样的事情, 创建一个含有 $/ 子例程签名的同名函数。 它现在写在一行里面就很整洁了, 并且只重复 部分, 因为它不得不重复。

sub function-call( $/ ) {
     'say ' ~ $/<String>[0] ~ ' ~ ' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';'
}

say function-call( $/<Function-Call> );

对象化 #

一路上我做了相当多的选择, 让我们到达这里。这就是我们上次重构的地方:

my rule Number                { \d+                                                          };
my rule Variable              { \w+                                                          };
my rule String                { '"' <-[ " ]>+ '"'                                            };
my rule Assignment-Expression { var <Variable> '=' <Number>                                  };
my rule Function-Call         { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };

'var a = 3; console.log( "Hey, did you know a = " + a + "?" );' ~~ rule { <Assignment-Expression> ';' <Function-Call> ';' }

sub assignment-expression( $/ ) {
    'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
}

sub function-call( $/ ) {
    'say ' ~ $/<String>[0] ~ ' ~ $' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';';
}

say assignment-expression( $/<Assignment-Expression> );
say function-call( $/<Function-Call> );

这就是我们的回报。我们先捡起最后那两个 say 语句。 我们还没有给顶层 rule 一个名字, 所以我们就叫它… 好吧, 现在还是叫 ‘top’ 吧。

sub top( $/ ) { assignment-expression( $/ ) ~ function-call( $/ ) }

收回你的吐槽 #

我们暂时还没有对处于文件顶层的 rules 做太多处理, 所以让我们开始工作吧。 在 Raku 中, 就一般编程而言, 把你的代码打包复用是不错的注意。而 Raku 让我们使用 class 关键字将我们的程序打包, 我们拥有的那些 rules 从任何意义上来说实际上不是"代码”。而它们能够用于代码中, 并且我们确实使用了它们, 它们自身实际上并没有做出任何决定。

所以我们不应该使用 class 关键字来把它们打包到一块。相反, 有另外一种便捷的类型用于把一堆正则表达式和 rules 打包到一块儿, 它叫做 grammar

它的语法就像声明一个「rule」 那样。

grammar Javascript {
    rule Number                { \d+                                                          };
    rule Variable              { \w+                                                          };
    rule String                { '"' <-[ " ]>+ '"'                                            };
    rule Assignment-Expression { var <Variable> '=' <Number>                                  };
    rule Function-Call         { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };      

    rule TOP                   { <Assignment-Expression> ';' <Function-Call> ';'              };
}

你会注意到, 我们给我们的顶层 rule 也起了个名字, 并且暂时把它叫做 「TOP」 吧。 如果你正在家独自玩耍, 你可能已经做出更改并想知道 「‘var a = 3;…’ ~~ rule { … }」 是怎么起作用的, 因为键入诸如 「‘var a = 3;…’ ~~ JavaScript;」这样的东西可能不会那么有作用。

Grammars 就像类一样, 在里面它们实际上是一块可能的代码。 它们本身不会工作, 它们必须从潜在的转换为动态的代码。我们可以像你在类中做的那样:

my $JavaScript = JavaScript.new;

现在我们拥有了一个可以工作的变量。 现在, 让我们来使用它。所有的 Grammar 类都有一个内置的 「parse()」 方法, 以使我们能得到 grammar 中的正则表达式。 我们来修改我们的匹配语句以利用 parse() 方法:

$JavaScript.parse('var a = 3; console.log( "Hey, did you know a = " + a + "?" );');

我们的代码应该又能工作了。

接收动作 #

现在我们已经把我们所有的匹配的东西打包到一个小型的类里面了, 如果我们能对那些子例程做同样的处理将会很棒。 我们在这儿试试, 把我们的子例程放到它们自己的命名空间中, 就像我们对 rule 做的那样。 我们必须从 「sub」 修改为 「method」, 而我们的 「top」 方法将会使用 「self.」 去调用其它方法。

class Actions {
    method assignment-expression( $/ ) {
        'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
    }

    method function-call( $/ ) {
        'say ' ~ $/<String>[0] ~ ' ~ $' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';';
    }

    method top( $/ ) {
        self.assignment-expression( $/<Assignment-Expression> ) ~
        self.function-call( $/<Function-Call> )
    }
}

就像之前那样, 我们可以在一行里面创建 Actions 对象:

my $actions = Actions.new;

并且调用 top 几乎像我们之前做的那样:

say $actions.top( $/ );

我们已经修改了很多东西了, 所以我们来看看到哪了。

grammar JavaScript {
  rule Number                { \d+                                                          };
  rule Variable              { \w+                                                          };
  rule String                { '"' <-[ " ]>+ '"'                                            };
  rule Assignment-Expression { var <Variable> '=' <Number>                                  };
  rule Function-Call         { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };
  rule TOP                   { <Assignment-Expression> ';' <Function-Call> ';'              }
}
my $j = JavaScript.new;

$j.parse('var a = 3; console.log( "Hey, did you know a = " + a + "?" );');

class Actions {
    method assignment-expression( $/ ) {
      'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
    }

    method function-call( $/ ) {
      'say ' ~ $/<String>[0] ~ ' ~ $' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';';
    }

    method top( $/ ) {
      self.assignment-expression( $/<Assignment-Expression> ) ~
      self.function-call( $/<Function-Call> )
    }
}

my $actions = Actions.new;
say $actions.top($/);

不用担心, 我们快要到了。既然我们有了一个单独的类来处理 Actions, 我们把方法重命名为 Grammar 中所匹配的 rule 的名字, 以使我们不会忘记它们是什么。

class Actions {
    method Assignment-Expression( $/ ) {
        'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
    }

    method Function-Call( $/ ) {
        'say ' ~ $/<String>[0] ~ ' ~$' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';';
    }

    method TOP( $/ ) {
        self.Assignment-Expression( $/<Assignment-Expression> ) ~
        self.Function-Call( $/<Function-Call> )

    }
}

更进一步, 我们还有最后一点魔法能够利用。 我们将把 $javascript$actions 对象像这样组合在一块。

say $javascript.parse('...', :actions($actions) );

「:actions(…)」 给 「parse()」方法声明的可选参数。我们正告诉正则表达式引擎, 任何时候, 像 <Function-Call><TOP> 这样的 rule 匹配时, 我们会在我们的类中让它调用对应的同名方法。

这几乎是按原样工作的, 但是如果你运行修改后的代码, 你会发现解析返回了原来的匹配对象, 带着日语引用标记。所以看起来好像我们又回到了原地。不完全是。

继续, 我们在其中之一的方法中添加一个临时的 "say 'Hello';" 语句, 仅仅是为了确认它们正被调用。这是正则引擎正在工作并且可能正解析它所 going over 的一个重要证据。 你甚至可以使用某些我们上面已经学到的技巧然后写上 「say $/<Variable>;」 来查看匹配是否正像你想的那样运行。继续运行并玩玩, 做完的时候再回到这儿。

混合信号(Mixed Signals) #

正发生的是方法正被调用, 但是它们的输出被丢弃。我们来捕获输出然后使用 grammar 的最后一个特性, 抽象语法树。现在, 这可能会勾起坐在教室里看黑板上画出的盒子和线段的场景, 但是也没有那么糟糕了。我们已经看到了一个, 实际上 say() 的输出就是一个 AST。

我们来看下其它语法树, 我们在后台创建的那个。在 “$javascript.parse(…)” 调用的末尾添加上 「.ast」, 这会给我们展示我们自己创建的语法树。

如果你这样做了, 你会看到它打印了(Any), 这通常等价于「匹配失败」, 单是我们从之前的测试中知道匹配没有失败。所以这儿发生了什么? 当我们的方法运行的时候, 它们返回输出, 但是 Raku 不知道怎么处理这些输出, 或者说它不知道把输出安装到它所创建的 AST 中的哪个位置。

关键是一个叫做「make」的小东西。在方法的开头, 把这个添加到过去我们放置「say」的地方。

class Actions {
    method Assignment-Expression( $/ ) {
      make 'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
    }

    method Function-Call( $/ ) {
      make 'say ' ~ $/<String>[0] ~ ' ~ $' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';'
    }

    method TOP( $/ ) {
      make $/<Assignment-Expression>.ast ~ $/<Function-Call>.ast
    }
}

还有, 因为 Raku 为我们调用方法, 我们不需要自己来调用 self.Function-Call(...), 我们需要做的全部工作就是查看 Function-Call(...) 返回给我们的语法树。最终我们做到了。一个完整, 虽然微小的编译器。为了防止你在编辑时迷失, 这儿有一个最终的结果。

grammar JavaScript {
    rule Number                { \d+                                                          };
    rule Variable              { \w+                                                          };
    rule String                { '"' <-[ " ]>+ '"'                                            };
    rule Assignment-Expression { var <Variable> '=' <Number>                                  };
    rule Function-Call         { console '.' log '(' <String> '+' <Variable> '+' <String> ')' };
    rule TOP                   { <Assignment-Expression> ';' <Function-Call> ';'              }
}

class Actions {
    method Assignment-Expression( $/ ) {
        make 'my $' ~ $/<Variable> ~ ' = ' ~ $/<Number> ~ ';'
    }

    method Function-Call( $/ ) {
        make 'say ' ~ $/<String>[0] ~ ' ~ $' ~ $/<Variable> ~ ' ~ ' ~ $/<String>[1] ~ ';';
    }

    method TOP( $/ ) {
        make $/<Assignment-Expression>.ast ~ $/<Function-Call>.ast 
    }
}

my $j = JavaScript.new;
my $a = Actions.new;
say $j.parse(
   'var a = 3; console.log( "Hey, did you know a = " + a + "?" );',
   :actions($a)).ast;

到哪里去 #

一个简单但整洁的更改是你可以扩展 Assignment-Expression 来既接收数字又接收字符串。上次我们谈论了 rules 中的轮试,所以这个提示应该足够让你开始了:

rule Assignment-Expression { var <Variable> '=' (<Number> | <String>) }

你必须修改下 Assignment-Expression 方法以使它起作用。或者你可以狡猾一点然后发现( <Number> | <String> ) 可以转换为它自己的小的普通的 “Term” rule, “rule Term { | }”, 然后添加一个 action “method Term($/) { make $/ or $/}” 而只在 Assignment-Expression 中修改一个东西。

http://theperlfisher.blogspot.fr/2016/02/from-regular-expressions-to-grammars-pt_28.html