在python PLY（lex/yacc）中使用空生成规则时出现语法错误

2024-06-28 11:28:42 发布

您现在位置：Python中文网/ 问答频道 /正文
4452 3

这里给出了完整的示例：

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语法，“简介”是可选的。上面带有文本file1的代码运行良好。但是，当我从文本文件中将“Intro”部分作为文本文件2删除时，它在“body”部分给出了语法错误，这意味着它无法处理空的产品。请帮我解决这个错误如何处理我的代码的空生产规则？

错误消息： error message snip


Tags： lenreturninformationvaluedefintroductionprintlexer
1条回答
网友
1楼 · 发布于 2024-06-28 11:28:42

您的程序无法运行，因为您使用了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

CheckupInformation和statIntro之间的点表示进度。在一个有中间点的状态下，可能不止一个产品，这意味着解析器还没有弄清楚哪些选择。也有在开始时带有圆点的作品；这些将对应于紧跟在点之后的非终端，这表明现在需要考虑这些产品

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

必须在确认或根本不确认时执行减少。如果以下标记“先行标记”不能跟随要缩减的非终端，则可能不会执行缩减。一般来说，解析器需要考虑以下问题，这些问题可以通过咨询状态转换表（这些文件立即显示在产品后面）来立即回答：

  1. 在不执行缩减的情况下，是否可以继续使用下一个标记来进行分析？（这称为“移位”操作，因为解析器将活动产品中的一个令牌向右移位。）
  2. 对于这种状态下的每一种可能的缩减，解析是否可以通过执行该缩减来进行

如果以上问题的答案为“是”，则会发生冲突。这并不一定意味着语法是不明确的，但它确实意味着解析器无法决定如何在这两个选项中进行选择

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

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

Stat -> LPAREN CheckupInformation statIntro . statBody RPAREN

为了使该序列有效，解析器需要知道它将能够进行，这意味着前瞻标记（在本例中(）必须是状态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为空的情况

这似乎很多，但可能并非所有这些产品都是必要的。仅当可以启动可选组件的端子集和可以跟随它的符号集之间存在重叠时，才需要转换。因此，例如，如果B、C和D都可以以括号开头，但是A后面不能跟括号，那么optional_D不会引起冲突，只需要扩展B和C：

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

这需要一点语法分析来找出A后面会出现什么，但在普通语法中，这并不难手工完成

如果这看起来还是太多的作品，那么还有一些其他的可能性，这些可能性不那么普遍，但无论如何都可能有所帮助

首先，您可能认为在上述产品中呈现的顺序B、C和D并不重要。在这种情况下，您可以替换

A : optional_B optional_C optional_D

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

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

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

这允许对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]

如果这些都不令人满意，并且所有冲突都可以通过一个额外的前瞻令牌来解决，那么您可以尝试在lexer中解决这个问题

例如，您的语言似乎完全由S-exp组成以开括号开头，后跟某种关键字的表达式。因此，词法分析器可以将开括号和以下关键字组合成一个标记。一旦您这样做，您的可选组件就不再以相同的令牌开始，冲突也就消失了。（这种技术通常用于解析XML输入，这有一个相同的问题：如果所有感兴趣的内容都以<开头，那么冲突就会大量存在。但是如果您将<tag识别为单个标记，那么冲突就会消失。对于XML，在<之间不允许有空格。）和标记名；如果您的语法允许(和以下关键字之间有空格，您的lexer模式将变得稍微复杂一些，但仍然可以管理。）

相关问题 更多 >

    编程相关推荐