Bison解析器:语法规则、符号处理与多语法处理策略
1. 递归语法与栈大小控制
在某些情况下,一个包含5000条语句的程序可能会被解析为一个包含10000个元素(语句和分号)的列表。对于大多数Bison解析器来说,处理一个包含10000个元素的右递归列表可能会过大。右递归语法适用于那些已知较短且希望转换为值链表的项目列表,例如:
thinglist: THING { $$ = $1; } | THING thinglist { $1->next = $2; $$ = $1; } ;而左递归语法可能会导致列表以相反的顺序链接,需要在最后进行反转步骤,或者在每个阶段需要额外的代码来搜索列表的末尾,以便将下一个元素添加到末尾。
可以通过定义YYINITDEPTH和YYMAXDEPTH来控制解析器栈的大小。YYINITDEPTH是初始栈大小,通常为200;YYMAXDEPTH是最大栈大小,通常为10000。例如:
%{ #define YYMAXDEPTH 50000 %}每个栈条目包括一个语义值的大小(%union条目中最大的大小),加上两个字节的令牌编号,如果使用位置信息,还需要16个字节的位置信息。在具有1GB虚拟内存的工作站上,一个包含100000