1

Python で文字列を解析して括弧を追加する際に問題が発生しています。私の問題の 1 つは、文字列が完全に括弧で囲まれた方法で入力される場合があること (つまり(01U(1U0)))、またはまったくない場合があることです (つまり01U1U0)。私がそれを分割できないように見える文法は次のとおりです。

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

のe*優先順位は と よりも高くなりUます。

うまくいけば、これは理にかなっています。かっこを解析してチェックする方法を知っている人はいますか?

4

1 に答える 1

0

おそらく、LL 文法からパーサーを作成する最も簡単な方法は、非終端記号ごとに 1 つの関数を持つことです。この関数は、ルールの 1 つの削減に対応する入力文字列から文字を食べる必要があります。以下は、文法に対応するパーサーです

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

これはまさにあなたが望んでいた文法ではありませんが、あなたが示した例からはより適切でした. 文法は LL(1) で、1 文字読むだけで読み方がわかります。次のパーサーは、これらの 2 つの非終端記号に対して 2 つの関数 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 には 1 つの状態しかありません。オートマトンは次のように記述できます。

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 がありません。ただし、状態は 1 つしかないため、その必要はなく、ループで実行できます。

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 です。以前のパーサーは、暗黙的なスタックの代わりにプログラム スタックを使用し、再帰呼び出しの回数で読み込まれた括弧の数を記憶していました。この 2 番目のパーサーは、文字列の有効性を確認する場合に役立ちます。しかし、抽象構文ツリーのような入力の表現を生成したい場合には不便です: それらは通常、文法から構築されるため、最初のパーサーから生成する方が簡単です。最初のものは、理解するためにオートマトンを計算する必要がないため、読みやすくなっています。

于 2012-09-30T07:41:26.593 に答える