2

我正在使用 LL(k) EBNF 语法来解析字符流。我需要三种不同类型的令牌：

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是无效的，因为某些字符串可能同时是numand message（例如"123"），而其他字符串可能既是 anident又是 a message（例如"Hello"）。因此，分词器无法正确区分。

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

所以问题是，我可以用 LL(k) EBNF 语法来做到这一点吗？我正在使用CoCo/R来生成解析器和扫描器。

如果我不能用 LL(k) EBNF 做到这一点，那么我还可以考虑哪些其他选择？

编辑这是我从 CoCo/R 得到的输出：

可可/R（2010 年 4 月 23 日）
令牌双重和消息无法区分
令牌 ident 和 message 无法区分
...
检测到 9 个错误
4

3 回答 3

3

试试这个：

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 SPACE，您随后将使用“ - ' '”删除它。哦， 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将读取字符，直到它命中 ')' 或空格。我把它放在一个连接每个值的循环中，但你可能不想这样做。您可能希望将它放在一个循环中，这样当它看到“这里”而是“这里”时它不会返回“过度”。您可以对 messageText 进行简单的长度检查，或进行其他有效性检查，例如将 t.val 添加到 List 并检查计数。真的什么都有。您还可以使用 RegEx 进行测试，以确保它符合您需要检查的任何模式。

编辑（2011 年 4 月 8 日）： 使用带有整数和实数的 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.

编辑（2011 年 4 月 9 日）

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> ")"
.
于 2010-06-24T16:49:08.430 回答
2

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

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

我想不出使用 COCO/R 或类似方法来解决这个问题的方法，因为每个令牌都需要明确。

如果消息被引号或其他消除歧义的方式包围，那么您将不会有问题。我真的认为 PEG 可能是你的答案，因为它也有有序的选择（第一场比赛）。

也看看：

http://tinlizzie.org/ometa/

于 2010-06-21T06:22:42.950 回答
1

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

于 2010-06-15T14:44:08.657 回答