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

Syntax error using empty production rule in python PLY(lex/yacc)

这里给出了完整的例子:

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' 是可选的。带有文本文件 1 的上层代码运行良好。但是当我从文本文件中删除 'Intro' 部分作为文本文件 2 时,它在 'body' 部分给出语法错误,这意味着它无法处理空生产。请帮助我如何解决错误。 如何处理我的代码的空生产规则?

错误信息: error message snip

你的程序不能是运行因为你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 冲突的详细描述。检查该文件,我们发现以下内容:

state 3

    (1) Stat -> LPAREN CheckupInformation . statIntro statBody RPAREN
    (2) statIntro -> . LPAREN Introduction Name RPAREN
    (3) statIntro -> . statIntro LPAREN Introduction Name RPAREN
    (4) statIntro -> . empty
    (10) empty -> .

  ! shift/reduce conflict for LPAREN resolved as shift
    LPAREN          shift and go to state 4

  ! LPAREN          [ reduce using rule 10 (empty -> .) ]

    statIntro                      shift and go to state 5
    empty                          shift and go to state 6

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

Stat -> LPAREN CheckupInformation . statIntro statBody RPAREN

CheckupInformationstatIntro之间的点表示进度。中间有点的状态可能有不止一种产生式,这意味着解析器还没有确定要选择这些备选方案中的哪一个。也有以点开头的作品;这些将对应于紧跟在点之后的非终结符,表明现在需要考虑这些产生式。

也可能有结尾带点的产生式,表示此时在parse中,遇到的符号序列可以"reduced"到对应的非终结符。也就是说,解析器已经识别出非终结符。

减少必须在确认时执行,或者根本不执行。如果以下标记——"lookahead token"——不能跟随要减少的非终结符,则可能不会执行减少。通常,解析器需要考虑以下问题,这些问题可以通过查询状态转换立即得到回答 table(这些在产生式后立即显示):

  1. 解析是否可以通过继续下一个标记而不执行归约来进行? (这称为 "shift" 动作,因为解析器在活动产生式中将一个标记向右移动。)
  2. 对于此状态下的每个可能的缩减,解析是否可以通过执行该缩减来取得进展?

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

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

在这个状态的具体例子中,可以减少的是empty :。虽然从这个状态来看并不明显(我们必须看看解析器在进行归约后进入的状态,即状态 6),但在归约 empty 之后,解析器的下一步行动必然是归约 statIntro -> empty,之后它将进入状态 5,其中包括生产

Stat -> LPAREN CheckupInformation statIntro . statBody RPAREN

为了使该序列有效,解析器需要知道它能够继续进行,这意味着先行标记(在本例中 ()必须是 State 中的可能输入5.当然是因为statBody可以以左括号开头。所以可以减价了。

但是 statIntro 也可以以 ( 开头,因此解析器不必为了继续进行缩减。鉴于这两种选择,Ply 选择采取移位操作,这意味着它 丢弃 statIntro 可能为空的可能性 并假设 ( 属于一个statIntro。如果有 statIntro,这是正确的选择。但是如果statIntro少了,那么(就属于statBody,应该减去

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

在这种情况下,解决方法非常简单。只需要从 statIntro 中删除空产生式,而是通过为 Stat 提供两个产生式使其成为可选的,一个有 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 为空的情况。

这似乎很多,但可能并非所有这些作品都是必需的。仅当可以启动可选组件的终端集与可以跟随它的符号集之间存在重叠时才需要进行转换。因此,例如,如果 BCD 都可以以括号开头,但 A 后面不能跟括号,那么 optional_D 就不会导致冲突,只有 BC 需要扩展:

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

这需要一些语法分析来弄清楚后面可以跟什么 A,但在常见的语法中,手工完成并不难。

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

首先,您可能会认为在上述作品中 BCD 的顺序并不重要。在这种情况下,您可以替换

A : optional_B optional_C optional_D

使用不太复杂、更容易接受的替代方案:

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

(或者您可以通过在 A 的作品中单独写出备选方案来避免 X。)

这允许多次使用 BCD,但这似乎符合您的语法,其中可选组件实际上可能是空重复。

这留下了如何生成合理的 AST 的问题,但这很容易解决,至少在 Ply 的上下文中是这样。这是一个可能的实际解决方案,再次假设重复是 acceptable:

# 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]

如果您安排 BCD 的语义值以包含它们是什么的指示,则可以简化最后三个动作函数。因此,例如,如果 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]

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

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