防止 Marpa：：R2：：Scanless 中的朴素最长令牌匹配

在Marpa解析器中的无扫描接口（SLIF）的当前实现中，lexer似乎以以下方式进行最长令牌匹配（LTM）：

尝试在输入中的当前位置匹配所有终端符号
除最长的匹配项外，所有匹配项都将被丢弃
这些最长的令牌被提供给解析器，解析器可以接受也可以不接受它们
如果不接受任何令牌，则解析失败

当我的语法包含与最长子字符串匹配的标记，但不能出现在当前位置时，这会导致令人沮丧的解析失败。考虑以下代码：

#!/usr/bin/env perl
use strict; use warnings; use feature qw/say/; use utf8;
use Marpa::R2;
use Data::Dump;
my @data = ('! key : value', '! key:value');
my $grammar = Marpa::R2::Scanless::G->new({
    source => <<'END_GRAMMAR',
        :default ::= action => [values]
        :start   ::= record
        :discard  ~  ws
        ws        ~  [s]+
        record ::= ('!') key (':') value
        key     ~  [w]+
        value   ~  [^s]+
END_GRAMMAR
});

for my $data (@data) {
    my $recce = Marpa::R2::Scanless::R->new({
        grammar => $grammar,
        trace_terminals => 0, # set this to "1" to see how the tokens are recognized
    });
    $recce->read($data);
    my $val = $recce->value // die "no parse";
    say ">> $data";
    dd $$val;
}

这会产生输出：

>> ! key : value
["key", "value"]
Error in SLIF G1 read: No lexemes accepted at position 2
* Error was at end of input
* String before error: ! key:value
Marpa::R2 exception at marpa.pl line 33.

预期输出：

>> ! key : value
["key", "value"]
>> ! key:value
["key", "value"]

在识别出!之后，必须跟随一个key令牌。在该位置进行词法分析期间，value标记与最长的子字符串key:value匹配，尽管它不能出现在该位置。因此，解析失败。

问题：是否可以在不编写手动lexer的情况下实现预期输出？

（我知道lexer可以向识别器查询预期的令牌，并且可以将自己限制为只匹配这些令牌，但我不知道如何说服SLIF为我这样做。）

我正在perl5 v16.2 上运行Marpa:：R2 v2.064

编辑

根据Jeffrey Kegler的建议，我实现了一个规则，该规则将始终匹配比普通value更长的子字符串，因此是首选规则。使用pause事件，我可以手动解析它，尽管为了获得正确的语义，我必须保留一个幻影规则。

这是完整的更新代码，包括事件处理和更新的测试用例：

#!/usr/bin/env perl
use strict; use warnings; use feature qw/say/; use utf8;
use Marpa::R2;
use Data::Dump;
my @data = ('! key : value', '! key:value', '! key :value', '! key: value');
my $grammar = Marpa::R2::Scanless::G->new({
    source => <<'END_GRAMMAR',
        :default ::= action => [values]
        :start   ::= Record
        :discard  ~  ws
        ws        ~  [s]+
        Record ::=
                ('!') Key (<Op colon>) Value # not directly used
            |   ('!') KeyValue
        Key     ~  key
        Value   ~  value
        KeyValue~  key <ws any> ':' <ws any> value
        :lexeme ~ KeyValue pause => before event => 'before KeyValue'
        <Op colon> ~ ':'
        key     ~  [w]+
        value   ~  [^s]+
        <ws any>~  [s]*
END_GRAMMAR
});
my %events = (
    'before KeyValue' => sub {
        my ($recce, $string, $start, $length) = @_;
        my ($k, $o, $v) = split /(s*:s*)/, $string, 2;
        say STDERR qq(k="$k" o="$o" v="$v");
        my $pos = $start;
        $recce->lexeme_read('Key'      => $pos, length($k), $k);
        $pos += length $k;
        $recce->lexeme_read('Op colon' => $pos, length($o), $o);
        $pos += length $o;
        $recce->lexeme_read('Value'    => $pos, length($v), $v);
    },
);

for my $data (@data) {
    my $recce = Marpa::R2::Scanless::R->new({
        grammar => $grammar,
        trace_terminals => 0,
    });
    my $length = length $data;
    for (
        my $pos = $recce->read($data);
        $pos < $length;
        $pos = $recce->resume()
    ) {
        say STDERR "pause";
        my ($start, $length) = $recce->pause_span();
        my $str = substr $data, $start, $length;
        for my $event_data (@{ $recce->events }) {
            my ($name) = @$event_data;
            my $code = $events{$name} // die "no code for event $name";
            $recce->$code($str, $start, $length);
        }
    }
    my $val = $recce->value // die "no parse";
    say ">> $data";
    dd $$val;
}

这会产生

>> ! key : value
["key", "value"]
>> ! key:value
["key", "value"]
>> ! key :value
["key", "value"]
>> ! key: value
["key", "value"]

这是预期的行为。

请注意，自版本2.079_015以来，Marpa支持最长可接受令牌匹配的概念，这意味着只需添加：

lexeme default = forgiving => 1

你的语法将产生预期的输出。即：

#!env perl -w
use strict;
use Marpa::R2;
use Data::Dump;
use feature qw/say/;
my $grammar = Marpa::R2::Scanless::G->new({source => do {local $/; <DATA>}});
my @data = ('! key : value', '! key:value', '! key :value', '! key: value');
foreach (@data) {
    my $r = Marpa::R2::Scanless::R->new({grammar => $grammar});
    $r->read($_);
    my $val = $r->value;
    say ">> $_"; dd $$val;
}
__DATA__
:default ::= action => [values]
lexeme default = forgiving => 1
:start   ::= record
:discard  ~  ws
 ws        ~  [s]+
record ::= ('!') key (':') value
key     ~  [w]+
value   ~  [^s]+

将给出：

>> ! key : value
["key", "value"]
>> ! key:value
["key", "value"]
>> ! key :value
["key", "value"]
>> ! key: value
["key", "value"]

根据Ross的建议，从评论中复制：

您可以创建一个形式为record ::= ('!') <complex record>的规则，其中<complex record>不包含空格和两个或多个冒号。

"Pause before"<complex record>（使用pause_lexeme或events方法检查暂停）
将键、冒号和值分开，然后手动对它们进行lex
然后resume正常解析后记录

编辑

相关内容

最新更新

热门标签：