1

我正在尝试编写一个没有回溯的递归下降解析器，用于像这样的 EBNF：

<a> ::= b [c] | d

在哪里

  • <a> = 非终端

  • 小写字符串 = 标识符

  • [term-in-brackets] = term-in-brackets 是可选的

  • a|b 是 a 和 b 之间通常互斥的选择。

现在，我只关心右手边。

按照http://en.wikipedia.org/wiki/Recursive_descent_parser中的示例，我最终得到了以下过程（上述评论中的 GNU bison 语法规则）：

/* expression: term optional_or_term */
void expression()
{
    term();
    if (sym == OR_SYM)
        optional_or_term();

}

/* optional_or_term: // empty
    | OR_SYM term optional_or_term
*/
void optional_or_term()
{
    while (sym == OR_SYM)
    {
        getsym();
        term();
    }
}

/* term: factor | factor term */
void term()
{
    factor();
    if (sym == EOF_SYM || sym == RIGHT_SQUAREB_SYM)
    {
        ;
    }
    else if (sym == IDENTIFIER_SYM || sym == LEFT_SQUAREB_SYM)
        term();
    else if (sym == OR_SYM)
        optional_or_term();
    else
    {
        error("term: syntax error");
        getsym();
    }

}

/*
factor: IDENTIFIER_SYM  
    | LEFT_SQUAREB_SYM expression RIGHT_SQUAREB_SYM
*/

void factor()
{
    if (accept(IDENTIFIER_SYM))
    {
        ;
    }
    else if (accept(LEFT_SQUAREB_SYM))
    {
        expression();
        expect(RIGHT_SQUAREB_SYM);
    }
    else
    {
        error("factor: syntax error");
        getsym();
    }

}

它似乎有效，但我的期望是每个程序都会与相应的规则密切对应。你会注意到 term() 没有。

我的问题是：在编写程序之前，语法是否需要更多的转换？

4

1 回答 1

1

我不认为你的问题是没有连接运算符。我认为它没有使用 Kleene 星（和加号）来列出事物。Kleene 星允许您在实现语法规则的过程中实际编写循环。

我会把你的语法写成： 

expression = term (OR_SYM term)*;
term = factor+;
factor = IDENTIFIER_SYM | LEFT_SQUAREB_SYM expression RIGHT_SQUAREB_SYM ;

（这是一个非常经典的语法语法）。

解析器代码如下所示：

 boolean function expression()
 {   if term()
     {   loop
         { if OR_SYM()
           {  if term()
              {}
              else syntax_error();
           }
           else return true;
         }
     else return false;
 }

 boolean term()
 {  if factor()
    {  loop
       {  if factor()
          {}
          else return true;
       }
    }
    else return false;
 }

 boolean factor()
 {  if IDENTIFIER(SYM)
    return true;
    else 
    { if LEFT_SQUAREB_SYM()
      {  if expression()
         {   if RIGHT_SQUAREB_SYM()
             return true;
             else syntax_error();
         }
         else syntax_error();
      else return false;
    }
 }

我试图以一种绝对机械的方式生成它，你可以像这样做得很好。在我的职业生涯早期，我做过很多这样的事情。

你不会得到的是每天 150 条工作规则。首先，对于一门大语言来说，语法很难正确；您将反复调整它以获得抽象的语法，然后您必须调整您编写的代码。接下来你会发现写词法分析器也有它的麻烦；只需尝试为 Java 编写一个词法分析器。最后，您会发现解析器规则不是整个游戏，甚至不是您工作的最大部分；你需要很多来处理真正的代码。我称之为“解析后的生活”；有关更多信息，请参阅我的简历。

如果您想每天获得 150 条工作规则，请切换到 GLR 解析器并手动停止编码解析器。这不会解决其他问题，但它确实让你在获得可用语法方面非常有效率。这就是我现在所做的。毫无例外。（我们的 DMS Software Reengineering Toolkit 使用了这个，我们解析了很多人们声称很难的东西。）

于 2014-09-30T14:31:33.027 回答