Yapp / yacc / bison - 语法
Yapp / yacc / bison - syntax
我正在尝试使用 Perl Yapp 编写解析器,据我所知,它与 yacc/bison 基本相同。
给我带来麻烦的输入如下所示:
interface someName
description "bla"
ip address 1.2.3.4 255.255.255.128
ip default-gateway 1.2.3.123
我的语法是这样的:
command:
INTERFACE IDENTIFIER if_attrs
| IP DEFAULT_GATEWAY IP_ADDRESS
;
if_attrs: # empty
| if_attrs if_attr
;
if_attr:
DESCRIPTION STRING
| IP ADDRESS IP_ADDRESS IP_ADDRESS
;
当然输入和整个语法要复杂得多,但这些是必不可少的部分。
生成标记有效(到目前为止我不关心缩进),但 运行 它抱怨“DEFAULT_GATEWAY”。
在阅读“IP”后,Yapp 还报告了 S/R 状态冲突,这对我来说有点意义,但我找不到解决方案。
我已经阅读了很多关于优先级技巧的文章并尝试了一些但没有成功。
非常感谢任何提示!
这里的根本问题是您的语法需要两个先行标记,这超出了 LALR(1) 解析器的范围。 (“1”表示前瞻仅限于一个标记。)
这不会使语言成为 LALR(2)。没有 LALR(2) 语言这样的东西,因为每一种具有 LALR(2) 文法的语言也都有 LALR(1) 文法。此外,有一种算法可以将 LALR(2) 文法转换为 LALR(1) 文法,甚至可以恢复由 LALR(2) 文法生成的解析树,如果您有一个实现.
不幸的是,这种转换生成的语法非常庞大且难以阅读,并且有很多产生式具有相同的语义动作。此外,转换的实现很少,因为更有效的策略是使用更通用的解析算法。可以要求 Bison 本身生成一个 GLR 解析器,在 Perl 中有 Jeffrey Kegler's Marpa parser,等等。但我假设您不想更改解析器生成器。
LALR(2)⇒LALR(1) 转换的基本性质是将第一个前瞻标记存储为语义值的一部分。这有效地将解析器一个标记转移到未来。如果您手动执行此操作,则仅非终端需要进行转换,实际上需要两个先行标记,在您的情况下,它基本上是代表命令列表的顶级非终端。
现在,我也不打算把它写出来。相反,我将提供两个更简单且可能更易于维护的技巧。
在词法分析器中消除歧义 ip
这是大多数类似 yacc 的处理器处理语法描述中的可选 ;
的方式。 (我不知道分号在 yapp 中是否是可选的,但它肯定在 yacc 和 bison 中是可选的。)在 BNF 语法中,如果标识符标记后跟 :
,则它明确地位于左侧,但是一个天真的实现是 LR(2),就像你的语法一样;在看到 :
之前,无法关闭之前的定义。为解决此问题,词法分析器将后跟 :
的标识符识别为不同的标记类型。同样,您的词法分析器可以将两个标记序列 ip default-gateway
识别为单个标记。这假设在语法中没有其他地方 ip
可以紧跟 default-gateway
,或者如果是的话,它可以被解析为好像它是一个单独的世界。
这会使词法分析器变得有点复杂(特别是如果您允许在两个关键字之间进行注释),但如果您只有几个必须以这种方式识别的短语,那可能还不错。
即时建立界面命令
这里,顶级非终结符分为两种可能:
- closed,意思是最后一条命令不能扩展,
- open,意思是最后一个命令是接口命令,后面要追加
if_attr
子句。
open 非终端的语义值包括可能不完整的接口命令作为其语义值的一部分。
这也是基于解析BNF的策略,其中单个标识符只保留在生产列表的语义值中,直到清楚是否要将其添加到右侧最后一部作品或它是新作品的左侧。
我已经很多年没有用 Perl 编程了,所以我把语义动作写成了伪代码。对不起。
# A list of commands
closed_program:
%empty
| closed_program unambiguous_command {
push($_[1], $_[2]); # Add the command to the end of the list
}
| open_program unambigous_command {
push($_[1]{"list"}, $_[1]{"saved"});
# The saved command is now complete
push($_[1]{"list"}, $_[2]);
# Also add the new complete command
}
# Semantic value has two attributes:
# * "list" is a list of commands
# * "saved" is an interface command
open_program:
closed_program interface_identifier {
# return {list => $_[1], saved => $_[2]}
}
| open_program if_attr {
# add $_[2] to the "saved" entry of $_[1]
}
unambiguous_command:
default_gateway_command
| ... # other commands which cannot be clauses
;
default_gateway_command:
IP DEFAULT_GATEWAY IP_ADDRESS
;
# Action needs to create a new interface command
# with an empty list of attributes
interface_identifier:
INTERFACE IDENTIFIER
;
# Action creates an attribute (however that is represented)
# which will be added to the attribute list
if_attr:
DESCRIPTION STRING
| IP ADDRESS IP_ADDRESS IP_ADDRESS
;
另一种可能比 rici 的方法更简单的替代方法是独立解析行,然后尝试将它们组合在一起。你可能有这样的东西:
input: /*empty*/ | input line ;
line:
INTERFACE IDENTIFIER '\n' {
lines.push_back(Interface(... }
| IP DEFAULT_GATEWAY IP_ADDRESS '\n' {
lines.push_back(DefaultGateway(... }
| DESCRIPTION STRING '\n' {
if (lines.back().isInterface()) {
lines.back().addDescription(...
} else {
error("description not associated with interface"); } }
| IP ADDRESS IP_ADDRESS IP_ADDRESS '\n' {
if (lines.back().isInterface()) {
lines.back().addAddress(...
} else {
error("address not associated with interface"); } }
;
请原谅没有使用特定语言的伪代码操作,但希望它们能说明这里需要什么。这对于强面向行的语法特别有效——因此这里的显式 '\n'
标记在这种情况下实际上不是必需的,但在其他情况下可能有用
我正在尝试使用 Perl Yapp 编写解析器,据我所知,它与 yacc/bison 基本相同。 给我带来麻烦的输入如下所示:
interface someName
description "bla"
ip address 1.2.3.4 255.255.255.128
ip default-gateway 1.2.3.123
我的语法是这样的:
command:
INTERFACE IDENTIFIER if_attrs
| IP DEFAULT_GATEWAY IP_ADDRESS
;
if_attrs: # empty
| if_attrs if_attr
;
if_attr:
DESCRIPTION STRING
| IP ADDRESS IP_ADDRESS IP_ADDRESS
;
当然输入和整个语法要复杂得多,但这些是必不可少的部分。
生成标记有效(到目前为止我不关心缩进),但 运行 它抱怨“DEFAULT_GATEWAY”。 在阅读“IP”后,Yapp 还报告了 S/R 状态冲突,这对我来说有点意义,但我找不到解决方案。 我已经阅读了很多关于优先级技巧的文章并尝试了一些但没有成功。
非常感谢任何提示!
这里的根本问题是您的语法需要两个先行标记,这超出了 LALR(1) 解析器的范围。 (“1”表示前瞻仅限于一个标记。)
这不会使语言成为 LALR(2)。没有 LALR(2) 语言这样的东西,因为每一种具有 LALR(2) 文法的语言也都有 LALR(1) 文法。此外,有一种算法可以将 LALR(2) 文法转换为 LALR(1) 文法,甚至可以恢复由 LALR(2) 文法生成的解析树,如果您有一个实现.
不幸的是,这种转换生成的语法非常庞大且难以阅读,并且有很多产生式具有相同的语义动作。此外,转换的实现很少,因为更有效的策略是使用更通用的解析算法。可以要求 Bison 本身生成一个 GLR 解析器,在 Perl 中有 Jeffrey Kegler's Marpa parser,等等。但我假设您不想更改解析器生成器。
LALR(2)⇒LALR(1) 转换的基本性质是将第一个前瞻标记存储为语义值的一部分。这有效地将解析器一个标记转移到未来。如果您手动执行此操作,则仅非终端需要进行转换,实际上需要两个先行标记,在您的情况下,它基本上是代表命令列表的顶级非终端。
现在,我也不打算把它写出来。相反,我将提供两个更简单且可能更易于维护的技巧。
在词法分析器中消除歧义 ip
这是大多数类似 yacc 的处理器处理语法描述中的可选 ;
的方式。 (我不知道分号在 yapp 中是否是可选的,但它肯定在 yacc 和 bison 中是可选的。)在 BNF 语法中,如果标识符标记后跟 :
,则它明确地位于左侧,但是一个天真的实现是 LR(2),就像你的语法一样;在看到 :
之前,无法关闭之前的定义。为解决此问题,词法分析器将后跟 :
的标识符识别为不同的标记类型。同样,您的词法分析器可以将两个标记序列 ip default-gateway
识别为单个标记。这假设在语法中没有其他地方 ip
可以紧跟 default-gateway
,或者如果是的话,它可以被解析为好像它是一个单独的世界。
这会使词法分析器变得有点复杂(特别是如果您允许在两个关键字之间进行注释),但如果您只有几个必须以这种方式识别的短语,那可能还不错。
即时建立界面命令
这里,顶级非终结符分为两种可能:
- closed,意思是最后一条命令不能扩展,
- open,意思是最后一个命令是接口命令,后面要追加
if_attr
子句。 open 非终端的语义值包括可能不完整的接口命令作为其语义值的一部分。
这也是基于解析BNF的策略,其中单个标识符只保留在生产列表的语义值中,直到清楚是否要将其添加到右侧最后一部作品或它是新作品的左侧。
我已经很多年没有用 Perl 编程了,所以我把语义动作写成了伪代码。对不起。
# A list of commands
closed_program:
%empty
| closed_program unambiguous_command {
push($_[1], $_[2]); # Add the command to the end of the list
}
| open_program unambigous_command {
push($_[1]{"list"}, $_[1]{"saved"});
# The saved command is now complete
push($_[1]{"list"}, $_[2]);
# Also add the new complete command
}
# Semantic value has two attributes:
# * "list" is a list of commands
# * "saved" is an interface command
open_program:
closed_program interface_identifier {
# return {list => $_[1], saved => $_[2]}
}
| open_program if_attr {
# add $_[2] to the "saved" entry of $_[1]
}
unambiguous_command:
default_gateway_command
| ... # other commands which cannot be clauses
;
default_gateway_command:
IP DEFAULT_GATEWAY IP_ADDRESS
;
# Action needs to create a new interface command
# with an empty list of attributes
interface_identifier:
INTERFACE IDENTIFIER
;
# Action creates an attribute (however that is represented)
# which will be added to the attribute list
if_attr:
DESCRIPTION STRING
| IP ADDRESS IP_ADDRESS IP_ADDRESS
;
另一种可能比 rici 的方法更简单的替代方法是独立解析行,然后尝试将它们组合在一起。你可能有这样的东西:
input: /*empty*/ | input line ;
line:
INTERFACE IDENTIFIER '\n' {
lines.push_back(Interface(... }
| IP DEFAULT_GATEWAY IP_ADDRESS '\n' {
lines.push_back(DefaultGateway(... }
| DESCRIPTION STRING '\n' {
if (lines.back().isInterface()) {
lines.back().addDescription(...
} else {
error("description not associated with interface"); } }
| IP ADDRESS IP_ADDRESS IP_ADDRESS '\n' {
if (lines.back().isInterface()) {
lines.back().addAddress(...
} else {
error("address not associated with interface"); } }
;
请原谅没有使用特定语言的伪代码操作,但希望它们能说明这里需要什么。这对于强面向行的语法特别有效——因此这里的显式 '\n'
标记在这种情况下实际上不是必需的,但在其他情况下可能有用