为什么我定义的语法不使用标记？

Question

我正在使用 lex 和 yacc 定义一种新语言。词法分析器工作正常但解析器没有。我认为问题是语法无法识别标记，但经过大量研究和试验后，我真的被困住了。我不太确定语法是否完全正确。我从解析器收到“输入语法错误”，但数据中没有语法错误。

数据输入为：

F 100

这里是这个语法的另一个例子：

L 36 [L 4 [F 100 R 90] R 10]

我的词法分析器（lexing.py）代码：

import lex

tokens = (
    'NUMBER',
    'RED',
    'GREEN',
    'BLUE',
    'BLACK',
    'FORW',
    'RIGHT',
    'LOOP',
    'COLOR',
    'PEN',
    'LSQB',
    'RSQB',
    'EMPTY'
) 

t_FORW    = r'F'
t_RIGHT   = r'R'
t_LOOP   = r'L'
t_COLOR  = r'COLOR'
t_PEN  = r'PEN'
t_LSQB  = r'\['
t_RSQB  = r'\]'
t_RED  = r'K'
t_GREEN  = r'Y'
t_BLUE  = r'M'
t_BLACK  = r'S'
t_EMPTY = r'\ ' 

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)    
    return t 

def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value) 

t_ignore  = ' \t' 

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1) 

lexer = lex.lex()


data = '''
F 100
''' 

lexer.input(data)
 
for tok in lexer:
    print(tok)

这里是解析代码：

import yacc
from lexing import tokens


def p_root(p):
    '''root : function NUMBER option
            | COLOR colors option
            | PEN NUMBER option '''
    
def p_option(p):
    '''option : root
              | LSQB root RSQB root
              | EMPTY '''
def p_function(p):
    '''function : FORW 
                | RIGHT 
                | LOOP '''
    
def p_colors(p):
    '''colors : RED 
              | BLUE 
              | GREEN 
              | BLACK ''' 
              
def p_error(p):
    print("Syntax error in input!")

from lexing import data

# Build the parser

parser=yacc.yacc()
result=parser.parse(data)
#print (result)

我尝试了所有我知道的方法。如您所见，我还没有编写 p 参数，但尝试编写它并不是解决方案。真正的问题可能是什么？

Answer 1

眼前的问题是您使用 EMPTY 作为标记（单个 space 字符）。该定义与 t_ignore 中的忽略字符列表冲突，这也将成为一个问题。但是请注意，你输入的末尾没有space字符（输入以换行符结尾，忽略），你的语法要求option以EMPTY结尾。这肯定会产生语法错误。（在这个答案的第一个版本中，我说 t_ignore 被显式标记模式覆盖，但事实证明我错了。您可以在 中使用忽略的字符 规则，但不在开头；永远不会匹配以被忽略的字符开头的标记。）

特别是如果这是您的第一个项目，您应该遵循更系统的调试技术。首先确保输入以您期望的方式进行标记化，而不是尝试解析标记流。当您开始解析流时，请确保任何语法错误都会报告产生错误的标记，包括它在输入中的位置。

可以使用关键字参数 debug=True 调用词法分析器和解析器，这将提供解析器操作的调试日志。那绝对应该是你调试的一部分。

综上所述，我觉得您的语法对于确定输入的结构不是很有用。良好的语法阅读方式与您用自己的语言描述输入的方式相同，其中可能包括如下描述：

输入的是命令列表。
命令可以是前向命令、右命令...或循环命令。
转发命令是 F 后跟一个数字。
循环命令是 L 后跟一个数字，然后是 [ 和 ].

Answer 2

我终于解决了。代码是完美的，真正的问题是我和我荒谬的语法。

以前的语法是：

<root> ::= <function> <numbers> <option> | COLOR <colors> <option> | PEN <numbers> <option>
<option>::= <root> | [ <root> ] <root> | ε
<function>::= F | R | L
<colors>::= K | M | Y | S

新语法是：

<grammar> ::= <function> | <function> <grammar> | ε 
<function> ::= <forward> | <right> | <loop> | <color> | <pen>
<forward> ::= F <numbers> 
<right> ::= R <numbers>
<loop> ::= L <numbers> <lbracket> <grammar> <rbracket>
<color> ::= COLOR <colors>
<pen> ::= PEN <numbers>
<colors> ::= M | K | S | Y
<lbracket> ::= [
<rbracket> ::= ]

并且我删除了 EMPTY 标记并定义了新规则而不是那个。我使用的 yacc.py 文件包含使用 ε 的特殊值。这是代码的语法定义部分：

def p_start(p):
    '''start : function 
             | function option'''
def p_function(p):
    '''function : forward 
                | right 
                | loop
                | color
                | pen'''
def p_empty(p):
    'empty :'
    pass
def p_option(p):
    '''option : start 
              | empty '''
def p_forward(p):
    'forward : FORW NUMBER'
def p_right(p):
    'right : RIGHT NUMBER'
def p_loop(p):
    'loop : LOOP NUMBER LSQB start RSQB'
def p_color(p):
    'color : COLOR colors'
def p_colors(p):
    '''colors : BLACK 
              | BLUE
              | GREEN
              | RED '''
def p_pen(p):
    'pen : PEN NUMBER'
    
def p_error(p):
   print("Syntax error in input!")

为什么我定义的语法不使用标记？

Why does the grammar I defined not use tokens?

python

yacc

lex

ply

pushdown-automaton