在 python PLY(lex/yacc) 中使用空生产规则的语法错误

Question

这里给出了完整的例子：

import ply.lex as lex
import Property
# List of token names.   This is always required
tokens = [
    'CheckupInformation',
    'Introduction',
    'Information',
    'perfect',
    'sick',
    'LPAREN',
    'RPAREN',
    'CHAR',
    'NUMBER'
    ] 
def t_CheckupInformation(t)     : 'CheckupInformation'     ; return t
def t_Introduction(t)  : 'Introduction'  ; return t
def t_Information(t) : 'Information' ; return t
def t_perfect(t): 'perfect'; return t
def t_sick(t) : 'sick'; return t



t_LPAREN  = r'\('
t_RPAREN  = r'\)'
t_CHAR = r'[a-zA-Z_][a-zA-Z0-9_\-]*'
t_ignore = " \t"
# Define a rule so we can track line numbers

def t_NUMBER(t):
    r'[+\-0-9_][0-9_]*'
    t.lexer.lineno += len(t.value)
    try:
        t.value = int(t.value)
    except ValueError:
        print("Integer value too large %s" % t.value)
        t.value = 0
    return t
def t_SEMICOLON(t):
    r'\;.*'
    t.lexer.lineno += len(t.value)
def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)
# Error handling rule
def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

 # Build the lexer
lexer = lex.lex()
# define upper level classes first     
class stat:
    def __init__(self):
        self.statement = ""
        self.intro = list()
        self.body = list()


P=stat()
def p_stat(p):
    'Stat : LPAREN CheckupInformation statIntro statBody RPAREN'
    p[0]=(p[1],p[2],p[3],p[4],p[5])

def p_Intro(p) : 
    '''statIntro : LPAREN Introduction Name RPAREN
                 | statIntro LPAREN Introduction Name RPAREN
                 | empty'''

    if len(p)==5:
       p[0] = (p[3])
    elif len(p)==6:
       p[0] = (p[4])
    else:
       p[0]= None
    P.intro.append(p[0])

def p_Name(p):
    'Name : CHAR'
    p[0]=p[1]



def p_Body(p):
    '''statBody : LPAREN Information bodyinfo RPAREN
                | statBody LPAREN Information bodyinfo RPAREN'''
    if len(p)==5:
       p[0] = (p[3])
    elif len(p)==6:
       p[0] = (p[4])
    P.body.append(p[0])
def p_bodyinfo(p):
    '''bodyinfo : LPAREN CHAR perfect RPAREN
                | LPAREN CHAR sick RPAREN'''
    p[0]=p[2],p[3]


def p_empty(p):
    'empty :  '
    print("This function is called")
    pass   
def p_error(p):
    print("Syntax error in input '%s'!" % p.value)

import ply.yacc as yacc
parser = yacc.yacc()
import sys
if len(sys.argv) < 2 :
    sys.exit("Usage: %s <filename>" % sys.argv[0])
fp = open(sys.argv[1])
contents=fp.read()
result=parser.parse(contents)

print("(CheckupInformation")
if (P.intro) != None:
    for x in range(len(P.intro)):
        print("    (Introduction %s)" %(P.intro[x]))
for x in range(len(P.body)):
        print("    (Information( %s %s))" %(P.body[x]))
print(")")

文本文件 1 是：

(CheckupInformation
  (Introduction John)
  (Introduction Patt)
  (Information(Anonymous1 perfect))
  (Information(Anonymous2 sick))
)

文本文件 2 是：

(CheckupInformation
  (Information(Anonymous1 perfect))
  (Information(Anonymous2 sick))
)

根据我的 bnf 语法，'Intro' 是可选的。带有文本 file1 的上层代码运行良好。但是，当我从文本文件中删除“介绍”部分作为文本文件 2 时，它会在“正文”部分出现语法错误，这意味着它无法处理空生产。请帮助我如何解决错误。如何处理我的代码的空生产规则？

错误信息： 错误信息截图

Answer 1

您的程序无法运行，因为您import Property不是标准库模块。但是删除该行至少足以到达 Ply 尝试构建解析器的地步，此时它会生成几个警告，包括一个 shift/reduce 冲突警告。最后一个警告很重要；你应该尝试修复它，你当然不应该忽视它。（这意味着您应该将其报告为问题的一部分。）正是这种冲突阻止了您的解析器工作。

这是它所说的：

WARNING: Token 'NUMBER' defined, but not used
WARNING: There is 1 unused token
Generating LALR tables
WARNING: 1 shift/reduce conflict

Ply 生成文件parser.out，其中包含有关您的语法的更多信息，包括对 shift/reduce 冲突的详细描述。检查该文件，我们发现以下内容：

WARNING: Token 'NUMBER' defined, but not used
WARNING: There is 1 unused token
Generating LALR tables
WARNING: 1 shift/reduce conflict

解析器在处理 时进入状态 3 Stat：

Stat -> LPAREN CheckupInformation . statIntro statBody RPAREN

CheckupInformation和之间的点statIntro表示进度。在中间有点的状态下可能有不止一个产生式，这意味着解析器还不必弄清楚要选择哪些替代方案。也有以点开头的作品；这些将对应于紧跟在点之后的非终结符，表明现在需要考虑这些产生式。

也可能有结尾带点的产生式，这表示在解析中的这一点，遇到的符号序列可以“减少”到相应的非终结符。换句话说，解析器已经识别出非终结符。

减少必须在被认可时执行，或者根本不执行。如果以下记号——“先行记号”——不能跟随要归约的非终结符，则可能不会执行归约。通常，解析器需要考虑以下问题，这些问题可以通过查阅状态转换表立即得到解答（这些问题会在产生式之后立即显示）：

1. 解析是否可以通过继续下一个标记而不执行归约来进行？（这称为“移位”操作，因为解析器在活动产生式中向右移位一个标记。）
2. 对于这种状态下的每个可能的减少，解析是否可以通过执行该减少来进行？

如果对这些问题中的一个以上的答案是“是”，则会发生冲突。这并不一定意味着语法有歧义，但这确实意味着解析器无法决定如何在两种选择之间进行选择。

像大多数解析器生成器一样，Ply 使用一些内置规则解决了这个问题。其中一个规则是，在没有其他信息（优先声明）的情况下，如果第一个问题的答案是“是”，解析器应该继续进行而不执行任何归约。

在这种状态的特定示例中，可以进行的减少是empty :。虽然从这个状态看并不明显（我们必须查看解析器在进行归约后进入的状态，即状态 6），但在归约之后empty，解析器的下一步必然是归约statIntro -> empty，之后它将转到状态 5，包括生产

Stat -> LPAREN CheckupInformation statIntro . statBody RPAREN

为了使该序列有效，解析器需要知道它将能够前进，这意味着先行标记（在本例中(）必须是状态 5 中的可能输入。当然，这是因为statBody可以开始带一个左括号。所以可以采取减少措施。

但statIntro也可以以 a 开头(，因此解析器不必为了继续进行减少而进行。给定这两种选择，Ply 选择采取 shift 操作，这意味着它丢弃statIntro可能为空的可能性并假设(属于 a statIntro。如果有statIntro，这是正确的选择。但如果statIntro缺少，则(属于statBody，并且应该减少。

所以这就是你的语法问题。这表明所写的语法需要不止一个前瞻标记。不幸的是，许多解析器生成器，包括 Ply，没有一种机制来处理需要多个前瞻标记的语法。（如果需要的前瞻数量有一些限制——例如，在这种情况下，可以通过查看接下来的两个标记来解决冲突——那么理论上可以找到相同语言的等效语法只需要一个前瞻令牌。但这必须是你的责任，因为 Ply 不会为你做。）

在这种情况下，解决方案非常简单。只需要从 中删除空的产生式statIntro，而是通过为 提供两个产生式来使其成为可选的Stat，一个有 a statIntro，一个没有：

def p_stat_1(p):
    'Stat : LPAREN CheckupInformation statIntro statBody RPAREN'
    p[0]=(p[1],p[2],p[3],p[4],p[5])

def p_stat_2(p):
    'Stat : LPAREN CheckupInformation           statBody RPAREN'
    p[0]=(p[1],p[2],None,p[3],p[4])

def p_Intro(p) :
    '''statIntro : LPAREN Introduction Name RPAREN
                 | statIntro LPAREN Introduction Name RPAREN
    '''

（我也p_empty从语法中删除了。）

此修改后的语法不会产生任何冲突，并将按预期解析您的测试输入：

$ python3 learner.py learner.1
(CheckupInformation
    (Introduction John)
    (Introduction Patt)
    (Information( Anonymous1 perfect))
    (Information( Anonymous2 sick))
)
$ python3 learner.py learner.2
(CheckupInformation
    (Information( Anonymous1 perfect))
    (Information( Anonymous2 sick))
)

后记：

上面建议的转换很简单，适用于很多情况，而不仅仅是可以通过两个标记的先行来解决冲突的情况。但是，正如评论中所指出的，它确实增加了语法的大小，特别是当产生式具有多个可选组件时。以生产为例：

A : optional_B optional_C optional_D

必须扩展为七种不同的产生式，一种用于来自 的每个非空选择B C D，此外，每个使用过的地方A都需要复制，以允许 为A空的情况。

这看起来很多，但可能并非所有这些作品都是必要的。仅当可以启动可选组件的终端集和可以跟随它的符号集之间存在重叠时，才需要转换。因此，举例来说，如果B，C并且D都可以启动一个括号，但A不能跟着一个括号，则optional_D不会造成冲突，并且只B和C需要进行扩展：

A : B C optional_D
  |   C optional_D
  | B   optional_D
  |     optional_D

这需要一些语法分析来弄清楚可以遵循什么A，但在普通语法中，手工完成并不太难。

如果这仍然看起来像太多的作品，还有其他一些不太普遍的可能性，但无论如何可能会有所帮助。

首先，您可能认为什么 order 并不重要B，C并且D在上面的制作中出现。在这种情况下，你可以更换

A : optional_B optional_C optional_D

不太复杂，更容易接受的替代方案：

A : 
  | A X
X : B | C | D

（或者您可以X通过在 的制作中单独写出替代品来避免A。）

这允许多次使用B,C和D，但这似乎与您的语法相对应，其中可选组件实际上可能是空重复。

这留下了如何生成合理的 AST 的问题，但这很容易解决，至少在 Ply 的上下文中。这是一种可能的实际解决方案，再次假设重复是可以接受的：

# This solution assumes that A cannot be followed by
# any token which might appear at the start of a component
def p_A(p):
    """ A : A1 """
    # Create the list of lists B, C, D, as in the original
    p[0] = [ p[1]["B"], p[1]["C"], p[1]["D"] ]

def p_A1_empty(p):
    """ A1 : """
    # Start with a dictionary of empty lists
    p[0] = { "A":[], "B":[], "C":[] }

def p_A1_B(p):
    """ A1 : A1 B """
    p[1]["B"].append(p[2])
    p[0] = p[1]

def p_A1_C(p):
    """ A1 : A1 C """
    p[1]["C"].append(p[2])
    p[0] = p[1]

def p_A1_D(p):
    """ A1 : A1 D """
    p[1]["D"].append(p[2])
    p[0] = p[1]

如果您安排 , 的语义值B，C并D包括它们是什么的指示，您可以简化最后三个动作函数。因此，例如，如果B返回["B", value]而不是value，那么您可以将最后三个A1操作合并为一个函数：

def p_A1_BCD(p):
    """ A1 : A1 B
           | A1 C
           | A1 D
    """
    p[1][p[2][0]].append(p[2][1])
    p[0] = p[1]

如果这些都不令人满意，并且所有冲突都可以通过一个额外的前瞻标记解决，那么您可以尝试在词法分析器中解决问题。

例如，您的语言似乎完全由 S 表达式组成，这些 S 表达式以开括号开头，后跟某种关键字。因此词法分析器可以将左括号与以下关键字组合成一个标记。一旦你这样做了，你的可选组件不再以相同的标记开始，冲突就会消失。（这种技术通常用于解析 XML 输入，它们具有相同的问题：如果所有有趣的东西都以 a 开头<，则冲突比比皆是。但如果您将其识别<tag为单个标记，则冲突就会消失。在 XML 的情况下，空格是<和标记名之间不允许；如果您的语法允许在(和以下关键字，您的词法分析器模式将变得稍微复杂一些。但它仍然可以管理。）