c++ - Lex/Yacc 语法

Question

我的任务涉及我学习语法(BNF 形式)并创建词法扫描器(使用 lex)和解析器(使用 bison)。我从来没有使用过这些程序中的任何一个，我认为一个很好的引用是查看这些项目是如何从语法创建的。我正在寻找一种语法及其关联的 .l 和 .ypp 文件，最好是在 C++ 中。我已经能够找到示例文件或示例语法，但不能同时找到它们。我花了一些时间搜索，但找不到任何东西。我想我会在这里发帖，希望有人能帮我找到一些东西，但同时我会继续搜索。

我目前正在阅读 Tom Niemann 的 http://epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf这似乎写得很好并且可以理解。

谢谢

编辑:我仍在搜索，我开始认为我正在寻找的东西不存在。 Google 通常不会让我失望!

编辑 2:也许如果我提供一些语法，你们可以告诉我合适的 .l 和 .ypp 文件是什么样子的。这只是语法的一个片段，我只需要稍微“尝一尝”它是如何工作的，我想我可以从那里得到它。

语法:

Program ::= Compound
Statements ::= Compound | Assignment | ...
Assignment ::= Var ASSIGN Expression
Expression ::= Var | Operator Expression Expression | Number
Compound := START Statements END
Number ::= NUMBER

说明:

Assignment is the equal sign ":="

Var is an identifier that begins with a lower case letter and is followed by lower case letters or digits

START is the "start" keyword

END is the "end keyword

Operator is "+", "-", "*", "/"

Number is decimal digits which could potentially be negative (minus sign in front)

Answer 1

其中大部分都相当简单。然而，有一部分确实有问题。您已经定义了一个数字(可能)包含一个前导 -，这是一个问题。

问题很简单。给定像 321-123 这样的输入，词法分析器(通常不会跟踪当前状态)基本上不可能猜测这是否应该是两个标记(321 和 -123 或三个 321、-、123)。在这种情况下，- 几乎肯定是要与 123 分开，但是如果输入是 321 + -123显然希望 -123 作为单个标记。

为了解决这个问题，您可能想要更改您的语法，以便前导- 不是数字的一部分。相反，您总是希望将 - 视为运算符，而数字本身仅由数字组成。然后由解析器对 - 是一元还是二进制的表达式进行分类。

考虑到这一点，词法分析器文件看起来像这样:

%{
#include "y.tab.h"
%}

%option noyywrap case-insensitive  
%%

:=        { return ASSIGN;   }
start     { return START;    }
end       { return END;      }
[+/*]     { return OPERATOR; }
-         { return MINUS;    }
[0-9]+    { return NUMBER;   }
[a-z][a-z0-9]* { return VAR; }
[ \r\n]   { ; }

%%

void yyerror(char const *s) { fputs(s, stderr); }

匹配的 yacc 文件看起来像这样:

%token ASSIGN START END OPERATOR MINUS NUMBER VAR
%left '-' '+' '*' '/'
%%

program : compound

statement : compound
            | assignment
            ;

assignment : VAR ASSIGN expression
            ;

statements :
            | statements statement
            ;

expression : VAR
            | expression OPERATOR expression 
            | expression MINUS expression
            | value
            ;

value: NUMBER
     | MINUS NUMBER
     ;          

compound : START statements END

%%

int main() {
    yyparse();
    return 0;
}

注意:我只对这些进行了最低限度的极度测试——足以验证我认为符合语法的输入，例如:start a:=1 b:=2 end 和 start a:=1+3*3 b:=a+4 c:=b*3 end 被接受(没有打印出错误消息)并且输入我认为是不符合语法的，例如as: 9:=13 和 a=13 do 都打印出 syntax error 消息。由于除了识别符合语法或不符合语法的表达式之外，这不会尝试对表达式做更多的事情，所以这大概是我们能做的最好的事情了。