1

我在解析字符串并在 Python 中为其添加括号时遇到问题。我的问题之一是字符串可能以完全带括号的方式输入（即(01U(1U0))），也可能根本没有输入（即01U1U0）。我似乎无法拆分的语法是：

A -> e* | (eUe)
e -> any combination of chars from the grammar

的e*优先级高于 和U。

希望这是有道理的。任何人都知道如何解析和检查括号？

4

1 回答 1

0

从 LL 语法编写解析器的最简单方法可能是每个非终结符号都有一个函数。这个函数应该吃掉输入字符串中对应于规则缩减的字符。下面是语法对应的解析器

A -> e+ | '(' A 'U' A ')'
e -> '0' | '1'

这不完全是您想要的语法，但与您提供的示例更相关。语法是 LL(1)，你只需要读一个字符就知道如何进行。以下解析器为这两个非终结符号定义了两个函数 A() 和 e() ：

class MySyntaxError(Exception):
  def __init__(self, text, index):
    self.text = text 
    self.index = index
  def __str__(self):
    return "Syntax error at index " + repr(self.index) + ": " + self.text


def parse(input):
  global index
  index = 0

  def eat_char(set):
    global index
    if index < len(input) and input[index] in set:
      index += 1
    else:
      raise MySyntaxError("expected char in " + repr(set), index)

  def e():
    eat_char(['0', '1'])

  def A():
    global index
    if index == len(input): # Successfully parsed
      return
    elif input[index] in ['0', '1']:
      while (input[index] in ['0', '1']):
        e()
    elif input[index] is '(':
      eat_char(['('])
      A()
      eat_char(['U'])
      A()
      eat_char([')'])
    else:
      raise MySyntaxError("expected char '0', '1' or '('", index)

  A()
  if index != len(input): # Parsing didn't reach the end of the string
    raise MySyntaxError("parsing ended before the end of the input", index)


def test(string):
  try:
    parse(string)
    print "The string " + string + " have been successfully parsed"
  except MySyntaxError as e:
    print "The string " + string + " can't be parsed:"
    print e

test("(01U(1U0))")
test("(01U(1U0)") # Missing parenthesis, syntax error
test("(01U(1U0)))") # Too many parenthesis, syntax error
test("01U(1U0)") # No parenthesis, syntax error

请注意，使用 e* 而不是 e+ 会使空归约为 A，这会使解析器复杂化。

下推自动机隐藏在解析器中。o 从语法构建自动机并不是那么简单。在这里，PDA 只有一种状态。我们可以这样描述自动机：

from state [1]
  read a '0' or a '1' and loop into state [1]
  read a '(', push the parenthesis and loop into state [1]
  read a 'U', when there is an open parenthesis on the top of stack, push the 'U' and loop into state [1]
  read a ')', when there is a 'U' on the top of the stack, pop the 'U', pop the opend parenthesis following, and loop into state[1]

有一种直接的方法可以用 Python 编写这个自动机。通常，你需要一个 goto 来编写一个自动机。每个状态都绑定到一个标签，从一个状态到另一个状态是通过 goto 完成的。不幸的是，Python 中没有 goto。但是，由于您只有一个状态，因此没有必要，并且可以使用循环：

def parse(input):
  index = 0
  stack = [];

  def top():
    if len(stack) > 0:
      return stack[len(stack)-1]
    else:
      return None

  while index < len(input):
    if input[index] in ['0', '1']:
      pass
    elif input[index] is '(':
      stack.append('(')
    elif input[index] is 'U' and top() == '(':
      stack.append('U')
    elif input[index] is ')' and top() == 'U':
      stack.pop()
      stack.pop()
    else:
      raise MySyntaxError("Unexpected char '" + input[index] + "'", index)
    index += 1

  if len(stack):
    raise MySyntaxError("unterminated input", index)

这是一个带有显式堆栈的 PDA。前面的解析器使用了程序栈而不是隐式栈，并且记住了递归调用次数中读取的括号次数。当您要检查字符串的有效性时，第二个解析器很有用。但是当你想生成输入的表示时，它就很不方便，比如抽象语法树：它们通常是从语法构建的，因此更容易从第一个解析器生成。第一个也更容易阅读，因为您无需计算自动机即可理解它。

于 2012-09-30T07:41:26.593 回答