时间戳

首页 > 解决方案 > 在 antlr4 语法中实现标记文本样式运算符时如何首先进行最短匹配？

parsing - 在 antlr4 语法中实现标记文本样式运算符时如何首先进行最短匹配？

问题描述

我在互联网上找到了以下（简化的）语法，因为我正在寻找一个解决问题的方法，我必须解析类似于 Markdown 的语法。

grammar Markdown;

parse    :   stat+;

stat    :   bold
        |   text
        |   WS
        ;

text    :   TEXT|SPACE;

bold    :   ('**'stat*'**');

TEXT    :   [a-zA-Z0-9]+;

SPACE   :   ' ';

WS      :   [\t\r\n]+;

我想要实现的是，antlr4 会首先在看起来像的句子上进行最短匹配**bold1** not bold **bold2**。这将意味着这bold1将是粗体not bold而不是粗体，并且bold2再次粗体。

但是，由于 antlr4 首先使用最长匹配，因此 antlr4 将示例解析为两个嵌套的粗体，这是错误的。

对于这个问题，我已经考虑过多种非常复杂的解决方案，但我实际上并不想使用这些解决方案。有简单的解决方案吗？

更新： 显然我简化了这个例子太多。现在这是一个扩展的语法（不再识别降价），但它说明了我遇到的问题。重要的是要注意，stat它也可以variable是我的语言可能包含的任何关键字的占位符。

grammar StyleParser;

parse    :   styled_stat+;

styled_stat : italic
            | bold
            | underline
            | stat
            ;

stat    :   variable
        |   text
        ;

variable: VARIABLE;
text    :   TEXT|SPACE;

italic  :   ITALIC (stat | italic_bold | italic_underline)* ITALIC;
italic_bold: BOLD (stat | italic_bold_underline)* BOLD;
italic_bold_underline: UNDERLINE stat* UNDERLINE;

italic_underline: UNDERLINE (stat | italic_underline_bold)* UNDERLINE;
italic_underline_bold: BOLD stat* BOLD;

bold    :   BOLD (stat | bold_italic | bold_underline)* BOLD;
bold_italic: ITALIC (stat | bold_italic_underline)* ITALIC;
bold_italic_underline: UNDERLINE stat* UNDERLINE;

bold_underline: UNDERLINE (stat | bold_underline_italic)* UNDERLINE;
bold_underline_italic: ITALIC stat* ITALIC;

underline   :   UNDERLINE (stat | underline_bold | underline_italic)* UNDERLINE;   
underline_italic: ITALIC (stat | underline_italic_bold)* ITALIC;
underline_italic_bold: BOLD stat* BOLD;

underline_bold: BOLD (stat | underline_bold_italic)* BOLD;
underline_bold_italic: ITALIC stat* ITALIC; 

SPACE   :   ' ';

VARIABLE : 'VAR';
TEXT    :   [a-zA-Z0-9]+;

ITALIC: '//';
BOLD: '==';
UNDERLINE: '__';

使用这种语法我不能嵌套相同的样式，但我可以嵌套不同的样式。例如，它可以==bold1 __underline //italic//__== not __underline__ //italic// bold ==VAR==正确解析。问题是规则的数量随着你引入的样式数量呈指数增长，我想避免这种情况。

标签： parsingantlrantlr4ll

解决方案

解析降价并非易事。一种方法是

  1. lex 本质上没有歧义的位；
  2. 在词法分析器发出时，评估每个语义上下文并酌情调整；
  3. 再次解析增强的词法分析器流，以使令牌序列本质上是非歧义的；
  4. tree-walk 来注释树或以其他方式构建以 Markdown 语法术语完全描述树元素的数据结构。

因此，对于 markdown-styled 的一般情况WORD，定义为一些不包括限定属性的文本字符串，解析器定义是

word
    : attrLeft* 
      w=( WORD | ENTITY | UNICODE
        | URL  | URLTAG | SPAN | HTML 
        )
      attrRight*
    ;

attrLeft  : LBOLD | LITALIC | LSTRIKE | LDQUOTE | LSQUOTE ;
attrRight : RBOLD | RITALIC | RSTRIKE | RDQUOTE | RSQUOTE ;

在词法分析器中，将所有属性定义为默认值，并为属性和left保留标记rightWORD

tokens {
    WORD,
    RBOLD,
    RITALIC,
    RSTRIKE,
    RDQUOTE,
    RSQUOTE
}

// attributes
LBOLD   : Bold   ;
LITALIC : Italic ;
LSTRIKE : Strike ;
LDQUOTE : Quote  ;
LSQUOTE : Mark   ;

... 

// last line in the lexer
CHAR : EscChar | . ;

在词法分析器superclass中，覆盖

public void emit(Token t) {...}

并决定是否

  1. 任何特定left属性都应该真正重新分配为right属性
  2. aCHAR应该累积到当前实例WORD中，或者应该添加到新WORD实例中。

现在，tree-walker 可以评估words 的序列并处理潜在的多个重叠嵌套属性的处理。

推荐阅读