代码之家 › 专栏 › 技术社区 › Drew Noakes

如何处理EBNF语法中不同标记中的重叠字符组?

ebnf grammar token language-agnostic parsing

Drew Noakes · 技术社区 · 16 年前

CHARACTERS

  letter = 'A'..'Z' + 'a'..'z' .
  digit = "0123456789" .
  messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')' .

TOKENS

  num = ['-'] digit { digit } [ '.' digit { digit } ] .
  ident = letter { letter | digit | '_' } .
  message = messageChar { messageChar } .

前两个标记声明很好,因为它们不共享任何公共字符。

但是第三个, message num 和 消息 (例如 "123" ident 和一个 (例如 "Hello" ). 因此,标记器无法正确区分。

另一个例子是区分整数和实数。除非您要求所有实数至少有一个小数位(意味着1需要编码为1.0,这对我来说不是一个选项),否则我无法在语法中得到这两种数字类型之间差异的支持。我必须用实数表示所有的值,并在点之后进行检查。这很好,但不是最理想的。我真正的问题是 消息 代币。我找不到解决办法。

所以问题是,我能用LL(k)EBNF语法吗?我在用 CoCo/R 生成解析器和扫描器。

如果我不能使用LL(k)EBNF,那么我还可以考虑哪些其他选项?

这是我从CoCo/R得到的输出:

Coco/R (Apr 23, 2010)
Tokens double and message cannot be distinguished
Tokens ident and message cannot be distinguished
...
9 errors detected

3 回复 | 直到 10 年前

Andre Artus 15 年前

试试这个:

CHARACTERS

    letter = 'A'..'Z' + 'a'..'z' .
    digit = "0123456789" .
    messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')'  .

TOKENS

    double = ['-'] digit { digit } [ '.' digit { digit } ] .
    ident = letter { letter | digit | '_' } .
    message = messageChar { messageChar } CONTEXT (")") .

'\u0020' 是unicode空间,您随后将使用 - ' ' ". 哦,你可以用 CONTEXT (')') ')' .

FWIW公司: CONTEXT 如果不使用封闭序列,则仍必须在生产中使用它。

编辑:

CHARACTERS
    letter = 'A'..'Z' + 'a'..'z' .
    digit = "0123456789" .
//    messageChar = '\u0020'..'\u007e' - ' ' - '(' - ')'  .

TOKENS

    double = ['-'] digit { digit } [ '.' digit { digit } ] .
    ident = letter { letter | digit | '_' } .
//    message = letter { messageChar } CONTEXT (')') .

// MessageText<out string m> = message               (. m = t.val; .)
// .

HearExpr<out HeardMessage message> =
    (.
        TimeSpan time; 
        Angle direction = Angle.NaN; 
        string messageText = ""; 
    .)
    "(hear" 
    TimeSpan<out time>
        ( "self" | AngleInDegrees<out direction> )
//         MessageText<out messageText>
    {
        ANY (. messageText += t.val; .)
    }
    ')'
    (. 
        message = new HeardMessage(time, direction, new Message(messageText)); 
    .)
    .

ANY 将读取字符,直到它碰到“)”或空白。我把它放在一个连接每个值的循环中,但您可能不想这样做。不过,您可能希望将它放在一个循环中,这样当它看到“over here”时就不会返回“over”,而是返回“here”。

使用带有整数和实数的Coco/R的示例

COMPILER Calculator
CHARACTERS
    digit       = "0123456789".

TOKENS
    intNumber    = ['-'] digit { digit } .
    realNumber   = ['-'] { digit } "." digit { digit } 
                         [("e" | "E") ["+" | "-"] digit {digit}] .

PRODUCTIONS
    Calculator  = { Expression "=" } .
    Expression  = Term { "+" Term | "-" Term }.
    Term        = Factor { "*" Factor | "/" Factor }.
    Factor      = intNumber | realNumber .

END Calculator.

Factor<out double value>
    (. value = 0.0; .)
= 
    ( 
        intNumber 
        (. value = Convert.ToDouble(t.val); .)
        | 
        realNumber 
        (. value = Convert.ToDouble(t.val); .)
    ) 
    | "(" Expression<out value> ")"         
.

或

Factor<out double value>
    (. value = 0.0; .)
=
    ( intNumber | realNumber ) 
    (. value = Convert.ToDouble(t.val); .)
    | "(" Expression<out value> ")"
.

Andre Artus 16 年前

您可能需要研究具有上下文敏感标记化的PEG生成器。

http://en.wikipedia.org/wiki/Parsing_expression_grammar

如果消息用引号括起来,或者用其他方法消除歧义,那么就不会有问题。我真的认为佩格可能是你的答案,因为它也有顺序的选择(第一场比赛)。

http://tinlizzie.org/ometa/

Jerry Coffin 16 年前

尽管有标题,这一切似乎都与扫描器有关,而不是与解析器有关。我没有使用CoCo/R,所以我不能直接对它进行评论,但是在一个典型的(例如lex/Flex)扫描器中,规则是按顺序考虑的,所以选择的规则/模式是第一个匹配的。我编写的大多数扫描仪都包含“.”(即匹配) 任何东西 )作为最后一种模式,如果有与任何其他规则不匹配的输入,则显示错误消息。