代码之家 › 专栏 › 技术社区 › Chris Tonkinson

上下文无关语法的奇怪问题

bison grammar language-design parsing

Chris Tonkinson · 技术社区 · 14 年前

我从一种语言的语法开始。变量, 二进制运算符、函数调用、列表、循环、条件等。在这个语法中,我想添加我称之为 object 构造:

object
  : object_name ARROW more_objects
  ;

more_objects
  : object_name
  | object_name ARROW more_objects
  ;

object_name
  : IDENTIFIER
  ;

关键是能够访问嵌套在对象中的标量。例如:

car->color
monster->weapon->damage
pc->tower->motherboard->socket_type

我在补充 对象 作为一个 primary_expression :

primary_expression
  : id_lookup
  | constant_value
  | '(' expression ')'
  | list_initialization
  | function_call
  | object
  ;

下面是一个示例脚本:

const list = [ 1, 2, 3, 4 ];
for var x in list {
  send "foo " + x + "!";
}
send "Done!";

在添加非终结符之前 对象 作为一个 主表达式 一切都是阳光和小狗。即使我加上它,野牛也不会抱怨。未报告转移和/或减少冲突。生成的代码编译时没有声音。但是当我尝试运行上面的示例脚本时,我被告知 error on line 2: Attempting to use undefined symbol '{' on line 2.

如果我将脚本更改为:

var list = 0;
for var x in [ 1, 2, 3, 4 ] {
  send "foo " + x + "!";
}
send "Done!";

然后我得到 error on line 3: Attempting to use undefined symbol '+' on line 3.

很明显 对象 在语法方面,我搞砸了解析器的行为,我觉得我忽略了一个相当简单的语言理论原则,它可以很快解决这个问题,但事实上没有任何移位/减少冲突让我困惑。

有没有更好的方法(语法上)来写这些规则?我错过了什么?为什么没有冲突?

(以下是 full grammar file 以备不时之需)

更新: 对象

正在使用访问的对象 对象

所以当我用我的语言写下:

player->name

只有编译器才能对其进行编码。”“玩家”和“名字”不是传统的 identifier s,因为它们没有添加到符号表中,并且在编译时除了将对播放器名称的请求转换为3地址代码外,对它们不做任何处理。

6 回复 | 直到 14 年前

Gian 14 年前

所以我花了相当长的时间仔细检查语法(和bison输出),看不出这里有什么明显的错误。如果没有执行它的手段,我就不能通过实验很容易地弄清楚到底发生了什么。因此,下面是我在调试语法时通常要经历的一些具体步骤。希望你可以做任何你还没有做过的事情,然后可能会发布后续(或编辑你的问题)的任何结果,可能会揭示:

根据您希望应用的规则,设计最小可能的工作输入和最小可能的非工作输入。
创建一个语法文件的副本,其中只包含麻烦的规则和尽可能少的其他支持规则(即,您需要一种只允许构建由 object more_object 规则,用箭头连接。这是否如你所期望的那样有效?
嵌套它的规则是否如您所期望的那样工作?尝试替换 对象 使用其他一些非常简单的规则(使用一些不在其他地方出现的标记),看看是否可以包含这些标记而不破坏其他所有内容。
与野牛赛跑 --report=all

查看错误输出的结构-“+”被识别为标识符标记,因此被查找为符号。也许值得检查一下lexer,看看它是如何处理标识符标记的。你可能只是不小心抓得太多了。作为一种进一步的调试技术,您可以考虑将其中的一些标记文字(例如,“+”、“{”等)转换为真正的标记,以便bison的错误报告可以为您提供更多帮助。

编辑:好吧,我越是深入研究它,我就越相信lexer不一定能正常工作。在继续下一步之前,我将再次检查您从yylex()获得的令牌流是否符合您的期望。特别是,一些正则表达式捕获了一堆您认为特殊的符号(例如“+”和“{”)或者至少允许传递标识符。

Community gview 7 年前

More on this here

Jonathan Leffler 14 年前

你不会因为你的规则使用 object_name more_objects 是右递归的,而不是Yacc(Bison)最自然地处理的左递归规则。

在经典的Yacc中,您会发现,如果嵌套足够深,堆栈空间就会耗尽 object->name->what->not '符号。Bison在运行时扩展了它的堆栈,因此必须耗尽内存,这比机器只有几兆字节(或更少)内存时要困难得多。

正确递归的一个结果是,在读取链中的最后一个对象名(或者更准确地说,在该名称之后的一个符号)之前,不会发生缩减。我看到你用了正确的递归 statement_list

Ira Baxter 14 年前

我认为你的主要问题是你没有定义一个子树构造函数对象

您可能还需要按遇到的顺序查找对象。也许你打算:

primary_expression 
   : constant_value                                        { $$ = $1; } 
   | '(' expression ')'                                    { $$ = $2; } 
   | list_initialization                                   { $$ = $1; } 
   | function_call                                         { $$ = $1; } 
   | object                                                { $$ = $1; } 
   ; 



object
   : IDENTIFIER    { $$ = LookupVariableOrObject( yytext ); } 
   |  object ARROW IDENTIFIER  { $$ = LookupSubobject( $1, yytext ); } 
   ;

我假设如果一个人遇到一个标识符X本身,你的默认解释它是一个变量名。但是,如果遇到X->Y、那么即使X 是一个变量名,您需要对象

最左边的 遇到标识符以查看它是否为变量或者查看它是否是有效的对象名,并返回标记为AST\u OBJ的AST节点, 或者如果标识符不是其中之一就抱怨。

LookupSubject所做的是检查其左操作数以确保它是AST\ OBJ (或名称恰好与对象的名称相同的AST\u VAR)。如果不是,就抱怨。如果是,那么它将查找的yytext子对象命名为AST_OBJ。

编辑:基于另一个答案中的讨论评论,右递归在OP的原始这个解决方案是递归的,不会与特定的陷阱相冲突。

ZXX 14 年前

id\U查找 :标识符

在形式上与

对象名称 :标识符

而object\u name会接受id\u lookup不会接受的所有内容,所以assertLookup(yytext);可能运行在所有看起来像标识符的东西上,而其他规则不接受这些东西,只是为了在2之间做出决定,然后object\u name不能接受,因为单个lookahead禁止这样做。

对于twilight区域,您得到错误的两个字符没有声明为标记,而opends是未定义行为的区域,当语法松动时,解析器可能会尝试将它们视为潜在的标识符。

Lolindrath 14 年前

我刚刚试着用bison2.4.1在ubuntu10.04中运行muscl,我能够运行你的两个例子,没有语法错误。我猜你的野牛版本里有个虫子。如果我运行的解析器有问题,请告诉我。下面是您给出的第一个示例的输出。

./muscle < ./test1.m (this was your first test)

\-statement list
  |-declaration (constant)
  | |-symbol reference
  | | \-list (constant)
  | \-list
  |   |-value
  |   | \-1
  |   |-value
  |   | \-2
  |   |-value
  |   | \-3
  |   \-value
  |     \-4
  |-loop (for-in)
  | |-symbol reference
  | | \-x (variable)
  | |-symbol reference
  | | \-list (constant)
  | \-statement list
  |   \-send statement
  |     \-binary op (addition)
  |       |-binary op (addition)
  |       | |-value
  |       | | \-foo 
  |       | \-symbol reference
  |       |   \-x (variable)
  |       \-value
  |         \-!
  \-send statement
    \-value
      \-Done!

 +-----+----------+-----------------------+-----------------------+
 |   1 | VALUE    | 1                     |                       |
 |   2 | ELMT     | @1                    |                       |
 |   3 | VALUE    | 2                     |                       |
 |   4 | ELMT     | @3                    |                       |
 |   5 | VALUE    | 3                     |                       |
 |   6 | ELMT     | @5                    |                       |
 |   7 | VALUE    | 4                     |                       |
 |   8 | ELMT     | @7                    |                       |
 |   9 | LIST     |                       |                       |
 |  10 | CONST    | @10                   | @9                    |
 |  11 | ITER_NEW | @11                   | @10                   |
 |  12 | BRA      | @14                   |                       |
 |  13 | ITER_INC | @11                   |                       |
 |  14 | ITER_END | @11                   |                       |
 |  15 | BRT      | @22                   |                       |
 |  16 | VALUE    | foo                   |                       |
 |  17 | ADD      | @16                   | @11                   |
 |  18 | VALUE    | !                     |                       |
 |  19 | ADD      | @17                   | @18                   |
 |  20 | SEND     | @19                   |                       |
 |  21 | BRA      | @13                   |                       |
 |  22 | VALUE    | Done!                 |                       |
 |  23 | SEND     | @22                   |                       |
 |  24 | HALT     |                       |                       |
 +-----+----------+-----------------------+-----------------------+
foo 1!
foo 2!
foo 3!
foo 4!
Done!