- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试使用 BNF 语法编写 Flex/Bison 文件。但是,当我尝试编译时出现错误,而且我不确定如何调试它们。
BNF语法:
<exp>::=<list> | head(<list>)
<list>::=<num1>::<list> | <list>@<list> | tail(<list>) | [<numlist>]
<numlist>::=<empty> | <num1><num2>
<num2>::=<empty> | ,<num1><num2>
<num1>::=<D1><N> | <N> | head(<list>)
<D1>::=<D1><N> | <D2>
<D2>::=[1-9]
<N>::=[0-9]
我的 Flex 文件
%option noyywrap
%{
#include <stdlib.h>
#include <list>
using namespace std;
#define YYSTYPE list<int>
#include "listop.tab.h"
%}
hd head
tl tail
ap [@()\[\]]
con ::
n [0-9]
d2 [1-9]
d1 ({d2}{n}+)|{d2}
ws[ \t\n]+
%%
{d1} yylval.clear(); yylval.push_front(atoi(yytext)); return D1;
{n} yylval.clear(); yylval.push_front(atoi(yytext)); return N;
{hd} return HEAD;
{tl} return TAIL;
{ap} return *yytext;
{con} return CON;
{ws} /* eat up white spaces */
%%
我的 Bison 文件
%{
#include <math.h>
#include <stdio.h>
#include <iostream>
#include <list>
using namespace std;
#define YYSTYPE list<int>
void outputlist(list<int>);
int yylex(void);
int yyerror(const char*);
list<int> a;
%}
%token N
%token D1
%token HEAD
%token TAIL
%right CON
%left '@'
%% /* Grammer rules and actions follow */
input: /* empty */
| input exp ;
exp: list '\n' {outputlist($1);}
| HEAD '(' list ')' '\n' {cout <<$3.front();} ;
list: num1 CON list {$3.push_front($1.front()); $$=$3;}
| list '@' list {$1.splice($1.end(),$3); $$=$1;}
| TAIL '(' list ')'{$$ = $3;}
| '[' numlist ']' {$$ = $2;};
numlist: /* empty */
| num1 num2 {$1.splice($1.end(), $2); $$=$1;};
num2: /* empty */
| ',' num1 num2 {$2.splice($2.end(),$3); $$=$2;};
num1: D1 N { $1.splice($1.end(), $2); $$=$1;}
| N { $$ = $1;}
| HEAD '(' list ')' {list<int> a; a.push_front($3.front()); $$=a;};
%%
int main() { return yyparse();}
int yyerror(const char* s) { cout << "error" << endl; return 0;}
void outputlist(list<int> list1)
{
cout << '[';
for (int i = list1.size(); i > 1; i --)
{
cout << list1.front() << ',';
list1.pop_front();
}
cout << list1.front();
list1.pop_front();
cout << ']' << endl;
}
自 YYSTYPE
已定义为 list<int>
在这两个文件的 C 声明部分,我使用库函数来插入/删除列表的头部、获取第一个元素等。
感谢任何帮助。谢谢。
编辑:我已经编辑了上面的 flex & bison 文件。我的程序现在运行了,但我没有得到正确的输出。这是我得到的:
输入:头([5,2,4])
输出:,错误
正确输出:5
最佳答案
使用可用的工具(例如 bison、C++ 编译器和 bison 手册)调试您的代码并不难。当您似乎正在学习如何在简单练习中使用 flex 和 bison 时,您可能需要有关如何完成调试的教程。如果您不需要教程,也许其他读者可能需要。接下来将是调试您的示例的教程。我目前正在计算机科学课上这样做,所以它会有老师的语气。
首先,我查看了您的 BNF。我注意到您似乎没有严格遵守 BNF notation而且布局有点乱。更好的版本是:
<exp> ::= <list>
| head ( <list> )
<list> ::= <num1> :: <list>
| <list> @ <list>
| tail ( <list> )
| [ <numlist> ]
<numlist> ::= <empty>
| <num1> <num2>
<num2> ::= <empty>
| , <num1> <num2>
<num1> ::= <D1> <N>
| <N> | head ( <list> )
<D1> ::= <D1> <N>
| <D2>
<D2> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<N> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<empty> ::=
了解布局如何提高可读性?您使用了 []
用于两个不同目的的符号,作为它们自己和指示字符集。字符集是一种灵活的表示法。 []
字符在扩展 BNF 中用作元字符,但它们用于表示选项而不是集合。您没有定义 <empty>
非终结符。尽管此示例遵循严格的符号,但为了防止终端和元符号之间的混淆,将使用引号,如:
<exp> ::= <list>
| head "(" <list> ")"
<list> ::= <num1> "::" <list>
| <list> "@" <list>
| tail "(" <list> ")"
| "[" <numlist> "]"
<numlist> ::= <empty>
| <num1> <num2>
<num2> ::= <empty>
| "," <num1> <num2>
<num1> ::= <D1> <N>
| <N> | head "(" <list> ")"
<D1> ::= <D1> <N>
| <D2>
<D2> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<N> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<empty> ::=
现在让我们来看看词法分析。如果我们按照@rici 的建议进行修复,并添加缺失的逗号,我们就有了这个规则:
ap [@()\[\],]
现在bison has an in-built debug capability这对于理解解析是如何工作的非常有用。为您的代码启用此功能可以清楚地看到它失败的地方。首先,我们必须启用跟踪,如手册中所述。我们需要做两件事:
yydebug
到非零-t
构建解析器(或 --debug
)选项因此在您的 listop.y
文件你应该改变main()
功能是:
int main() {
#ifdef YYDEBUG
extern int yydebug;
yydebug = 1;
#endif
return yyparse();}
重建 Bison :
bison listop.y -d -t
现在运行 flex 并重新编译:
flex listop.l
g++ -o listop.exe listop.tab.c lex.yy.c -DYYDEBUG -lfl
现在,当我们运行时,我们会得到一些诊断输出(对于您输入的 head([5,2,4])
):
Starting parse
Entering state 0
Reducing stack by rule 1 (line 25):
-> $$ = nterm input ()
Stack now 0
Entering state 1
Reading a token: head([5,2,4])
Next token is token HEAD ()
Shifting token HEAD ()
Entering state 5
Reading a token: Next token is token '(' ()
Shifting token '(' ()
Entering state 12
Reading a token: Next token is token '[' ()
Shifting token '[' ()
Entering state 7
Reading a token: Next token is token D1 ()
Shifting token D1 ()
Entering state 4
Reading a token: Next token is token ',' ()
error
Error: popping token D1 ()
Stack now 0 1 5 12 7
Error: popping token '[' ()
Stack now 0 1 5 12
Error: popping token '(' ()
Stack now 0 1 5
Error: popping token HEAD ()
Stack now 0 1
Error: popping nterm input ()
Stack now 0
Cleanup: discarding lookahead token ',' ()
Stack now 0
从这一行可以看出:
Reading a token: Next token is token D1 ()
数字 5 已作为标记返回 D1
由词法分析器。但是查阅BNF语法,我们可以看到它应该被视为 token N
。 .作为D1
和 N
包含它可以选择其中任何一个的相同数字。为什么选择D1
?这是因为模式/ Action 规则的顺序。较高的规则优先于较低的规则。要解决此问题,有必要更改规则的顺序:
{d1} yylval.clear(); yylval.push_front(atoi(yytext)); return D1;
{n} yylval.clear(); yylval.push_front(atoi(yytext)); return N;
到:
{n} yylval.clear(); yylval.push_front(atoi(yytext)); return N;
{d1} yylval.clear(); yylval.push_front(atoi(yytext)); return D1;
然后重新构建所有的部分。如果我们再试一次,我们会得到以下更长的轨迹:
Starting parse
Entering state 0
Reducing stack by rule 1 (line 25):
-> $$ = nterm input ()
Stack now 0
Entering state 1
Reading a token: head([5,2,4])
Next token is token HEAD ()
Shifting token HEAD ()
Entering state 5
Reading a token: Next token is token '(' ()
Shifting token '(' ()
Entering state 12
Reading a token: Next token is token '[' ()
Shifting token '[' ()
Entering state 7
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7
Entering state 16
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 24
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7 16 24
Entering state 31
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 24
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7 16 24 31 24
Entering state 31
Reading a token: Next token is token ']' ()
Reducing stack by rule 11 (line 35):
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16 24 31 24 31
Entering state 34
Reducing stack by rule 12 (line 36):
$1 = token ',' ()
$2 = nterm num1 ()
$3 = nterm num2 ()
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16 24 31
Entering state 34
Reducing stack by rule 12 (line 36):
$1 = token ',' ()
$2 = nterm num1 ()
$3 = nterm num2 ()
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16
Entering state 25
Reducing stack by rule 10 (line 34):
$1 = nterm num1 ()
$2 = nterm num2 ()
-> $$ = nterm numlist ()
Stack now 0 1 5 12 7
Entering state 15
Next token is token ']' ()
Shifting token ']' ()
Entering state 23
Reducing stack by rule 8 (line 32):
$1 = token '[' ()
$2 = nterm numlist ()
$3 = token ']' ()
-> $$ = nterm list ()
Stack now 0 1 5 12
Entering state 20
Reading a token: Next token is token ')' ()
Shifting token ')' ()
Entering state 28
Reading a token:
然而,预期的结果(5
)仍然没有输出。检查操作规则我们可以看到 outputlist
方法仅在 '\n'
时调用 token 匹配且跟踪不显示任何 '\n'
token 。这是因为它们在词法分析器中作为空格被删除。需要更改弹性规则以解决此问题:
ap [@()\[\],\n]
ws[ \t]+
再次重建。它现在可以工作,输出正确的值:
Starting parse
Entering state 0
Reducing stack by rule 1 (line 25):
-> $$ = nterm input ()
Stack now 0
Entering state 1
Reading a token: head([5,2,4])
Next token is token HEAD ()
Shifting token HEAD ()
Entering state 5
Reading a token: Next token is token '(' ()
Shifting token '(' ()
Entering state 12
Reading a token: Next token is token '[' ()
Shifting token '[' ()
Entering state 7
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7
Entering state 16
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 24
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7 16 24
Entering state 31
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 24
Reading a token: Next token is token N ()
Shifting token N ()
Entering state 3
Reducing stack by rule 14 (line 38):
$1 = token N ()
-> $$ = nterm num1 ()
Stack now 0 1 5 12 7 16 24 31 24
Entering state 31
Reading a token: Next token is token ']' ()
Reducing stack by rule 11 (line 35):
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16 24 31 24 31
Entering state 34
Reducing stack by rule 12 (line 36):
$1 = token ',' ()
$2 = nterm num1 ()
$3 = nterm num2 ()
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16 24 31
Entering state 34
Reducing stack by rule 12 (line 36):
$1 = token ',' ()
$2 = nterm num1 ()
$3 = nterm num2 ()
-> $$ = nterm num2 ()
Stack now 0 1 5 12 7 16
Entering state 25
Reducing stack by rule 10 (line 34):
$1 = nterm num1 ()
$2 = nterm num2 ()
-> $$ = nterm numlist ()
Stack now 0 1 5 12 7
Entering state 15
Next token is token ']' ()
Shifting token ']' ()
Entering state 23
Reducing stack by rule 8 (line 32):
$1 = token '[' ()
$2 = nterm numlist ()
$3 = token ']' ()
-> $$ = nterm list ()
Stack now 0 1 5 12
Entering state 20
Reading a token: Next token is token ')' ()
Shifting token ')' ()
Entering state 28
Reading a token: Next token is token '\n' ()
Shifting token '\n' ()
Entering state 32
Reducing stack by rule 4 (line 28):
$1 = token HEAD ()
$2 = token '(' ()
$3 = nterm list ()
$4 = token ')' ()
$5 = token '\n' ()
5-> $$ = nterm exp ()
Stack now 0 1
Entering state 8
Reducing stack by rule 2 (line 26):
$1 = nterm input ()
$2 = nterm exp ()
-> $$ = nterm input ()
Stack now 0
Entering state 1
Reading a token: ^Z
Now at end of input.
Shifting token $end ()
Entering state 2
Stack now 0 1 2
Cleanup: popping token $end ()
Cleanup: popping nterm input ()
实际上,尽管调试使程序可以运行,但它仍然是一种糟糕的方式。它不使用词法分析器来构建标记和解析器来匹配语法。所有的数字识别都应该在 flex 代码中完成。例如,为什么不使用这样的词法分析器:
%option noyywrap
%{
#include <stdlib.h>
#include <list>
using namespace std;
#define YYSTYPE list<int>
#include "listop.tab.h"
%}
hd head
tl tail
ap [@()\[\],\n]
con ::
n [0-9]
d2 [1-9]
num ({d2}+{n}?)|{n}
ws[ \t]+
%%
{num} return NUM; yylval.push_front(atoi(yytext));
{hd} return HEAD;
{tl} return TAIL;
{ap} return *yytext;
{con} return CON;
{ws} /* eat up white spaces */
%%
然后你可以稍微简化解析器中的语法,并使整体实现更简单。
我会把那部分留作练习。
关于bison - BNF 到 Flex/Bison,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33645123/
我正在写一个小语法作为类练习,我的教授并没有真正具体说明什么是合法的 BNF 表达式。 BNF 语法应该识别这种形式的字符串:AB、AABB、AAABBB、A...B...(一般形式:AnBn) 所以
如何将此 BNF 转换为 EBNF? ::= var ; ::= {;} ::= {,} : ::= {} ::= | | _ 最佳答案 EBNF 或 Extended Back
我正在开展一个学校项目,需要我解析 BNF 语法。我有点困惑管道符 (|)(我认为它的意思是“或”)在规则中扮演什么角色。 例如,如果我有以下内容: ::= b c d | e f g 哪个终端是
我需要将以下语法转换为 EBNF: -> = -> A|B|C -> + | * | * |( ) | 我目前取得的进展如下: -> = =
我正在尝试学习 BNF 并尝试组装一些 Z80 ASM 代码。由于我对这两个领域都是新手,我的问题是,我是否走在正确的轨道上?我正在尝试将 Z80 ASM 的格式编写为 EBNF,以便我可以找出从哪里
有谁知道我在哪里可以获得 LOGO 的 BNF 或 EBNF编程语言? 最佳答案 BNF 语法在某些情况下可能不太有用...... 编写一个与现有/历史实现准确兼容的 LOGO 并不是一件容易的事(我
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 1 年前。
最近在想下面的BNF A -> x | yA | yAzA where x,y,z are terminals. 我很确定这个语法是模棱两可的,但是如何使它不含糊呢? 最佳答案 如果一个特定的字符串可
是否有正则表达式的 BNF 语法? 最佳答案 你可以看到一个 Perl regexp (显示 a little more in detail here ,由 edg 发布) 关于正则表达式 BNF 语
我使用这个 BNF 来解析我的脚本: {identset} = {ASCII} - {"\{\}}; //<--all ascii charset except '\"' '{' and '}
无法为字符序列(可能为空)提出 BNF 语法,以逗号分隔,但不以逗号开头或结尾, 所以这没问题: ::= | , | 但这会产生类似 A, :-( 最佳答案 空字符序列给你带来了麻烦。您
我有一项作业要纠正一个不明确的 BNF,但我完全迷失了。我知道这不是一个真正的编程问题,如果这不是这些板的合适问题,我会很乐意删除它。有没有什么好的网站可以让我了解更多有关 BNF 的信息?我正在处理
我该如何描述语言 A → AA | ( A ) | ε 使用正则表达式生成? 最佳答案 正则表达式接受来自正则语言的字符串。 FSM 也可以接受常规语言。 在您的语言中,您必须匹配的括号数量可能是无限
在使用 Prolog DCG 解析输入时,最好有一个语法的 BNF 伴随。 例如: BNF ::= ::= ::= ::= a ::= the ::= cat ::= mou
我需要迭代形式的产生规则的符号: 例如:输入 ::= = | <> | = | > | in ::= | ; 所以我需要派生一个正则表达式来分割文本。这是我到目前为止所拥有的 (?:\s|^
我继承了一个 ANTLR 语法,现在我需要编写一个很好的、古老的、类似 YACC/BISON 的解析器(具体来说,我使用 PLY for python)。有许多奇怪的规则,我现在正在努力解决以下问题:
我需要解析一个不是我设计的简单专有语言,所以我不能改变语言。我需要 C# 中的结果,所以我一直在使用 TinyPG,因为它非常易于使用,并且不需要外部库来运行解析器。 TinyPG 生成一个简单的 L
最近我发现了 python 模块 pyparsing,这是一个通过编写语法而不是解析器来解析数据的好工具。我对上下文无关语法的概念还很陌生,所以请纠正这个问题中的任何错误假设。 Pyparsing 可
好吧,我不确定我应该如何使用递归下降解析来编写一个函数来解析如下语法。事实上,我不确定我是否做对了...... BNF: A : B | A '!' B : '[' ']' 伪代码: f() {
有一个我可以找到流行语言的Backus -Naur形式或BNF语法吗?每当我进行搜索时,我都不会出现太多,但是我认为它们必须在某个地方出版。我最有兴趣看到一个用于Objective-C和MySQL的一
我是一名优秀的程序员,十分优秀!