Yapp / yacc / bison - 语法

Question

我正在尝试使用 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 状态冲突，这对我来说有点意义，但我找不到解决方案。我已经阅读了很多关于优先级技巧的文章并尝试了一些但没有成功。

非常感谢任何提示！

Answer 1

这里的根本问题是您的语法需要两个先行标记，这超出了 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
;

Answer 2

另一种可能比 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' 标记在这种情况下实际上不是必需的，但在其他情况下可能有用

Yapp / yacc / bison - 语法

Yapp / yacc / bison - syntax

bison

yacc

在词法分析器中消除歧义 ip

即时建立界面命令

在词法分析器中消除歧义 `ip`