一覧CS-10-2 · 状態機械と言語

字句解析と構文解析

文字列をトークンへ分け、演算のまとまりと括弧の対応を学びます。

説明

プログラムの文字列は、まず数値や演算子などのトークンに分けられます。これが字句解析です。構文解析はトークンの並びを文法に従って組み立て、どの演算がどの部分を対象にするかという木構造を作ります。

12 + 3 * (4 - 1)をトークンへ分け、Pythonの構文木で加算・乗算・減算の関係を表示します。次に括弧だけをスタックで検査し、閉じ括弧が早すぎる場合や開き括弧が残る場合を調べます。文字の分割、括弧の対応、式全体の文法は別の検査です。

1数字のまとまりを一つにする

空白を除き、連続するASCII数字を一つの数値トークンとして取り出します。この式で使う演算子と括弧も個別に取り出します。

import re文字列のパターン処理; expression = '12 + 3 * (4 - 1)'対象の式; tokens = re.findall(r'[0-9]+|[+*()-]', expression)整数・演算子・括弧を抽出; tokensトークン列

12は1と2の二つではなく一つのトークンです。この簡単な抽出式は対象外の文字を無視するため、一般の入力検証にはそのまま使えません。今回は指定した式の構成を調べます。

2同じ文字でも優先順位がある

抽象構文木を作り、階層付きで表示します。ast.parseは解析だけを行い、式の値は計算しません。

import ast構文木を扱う; tree = ast.parse(expression, mode='eval')単一式として解析; print(ast.dump(tree, indent=2))木を階層表示

最上位の演算はAddです。左が12、右はMultで、乗算の右側にSub(4,1)があります。括弧そのものは木のノードとして残らず、減算が乗算の子になる構造へ反映されています。

3木の各部分を取り出す

根の演算、右の演算、その右の演算の種類を取り出します。

type(tree.body.op).__name__根の演算, type(tree.body.right.op).__name__右部分の演算, type(tree.body.right.right.op).__name__さらに右の演算, 12 + 3 * (4 - 1)同じ式の値

演算はAdd・Mult・Sub、計算値は21です。減算4-1を乗算の右引数にすることが、木の親子関係として表されています。

4括弧を変えると木が変わる

(12 + 3) * 4 - 1では、根が減算になります。文字として同じ数を使っていても、まとまりが変わります。

other = ast.parse('(12 + 3) * 4 - 1', mode='eval')括弧を変更; print(ast.dump(other, indent=2))別の木; (12 + 3) * 4 - 1変更後の値

計算値は59です。根Subの左がMult、その左がAddになっています。式を文字列の左から順に機械的に計算するだけでは、この優先順位を扱えません。

5括弧だけをスタックで調べる

開き括弧の位置を積み、閉じ括弧で直近の位置を取り出します。開きがないのに閉じが来たら、その位置で失敗します。

def brackets(text):括弧の検査 stack, trace = [], []開き位置と対応記録 for i, ch in enumerate(text):文字位置を走査 if ch == '(': stack.append(i)開きを積む elif ch == ')':閉じを処理 if not stack: return False, i, trace対応する開きがない trace.append((stack.pop(), i))直近の開きと対応 return not stack, stack, trace未閉鎖の有無と対応表

対応した開き・閉じの位置をtraceに残します。最後にstackが空なら括弧は対応済み、残っていれば未閉鎖の開き括弧があります。数値や演算子の文法までは調べません。

6入れ子と二種類の不一致

((1)+2)、1)、(1+2を順に検査します。

[(text, brackets(text)) for text in ['((1)+2)', '1)', '(1+2']]正常・余分な閉じ・未閉鎖

正常な式は内側(1,3)、外側(0,6)の順に対応します。1)は位置1で開きが足りず、(1+2は位置0の開きが最後まで残ります。最後に開いた括弧から閉じるため、スタックが適しています。

7括弧が合っても式とは限らない

1 + * 2には括弧の不一致がありませんが、演算子の並びが文法違反です。解析エラーの種類だけを返す関数で調べます。

def parse_status(text):式の解析結果 try:解析を試す ast.parse(text, mode='eval')単一式の文法検査 return 'accepted'解析成功 except SyntaxError as error:構文エラーを捕捉 return type(error).__name__例外の種類を返す

構文エラーは入力を解析する段階で分かります。括弧だけの検査では、演算子の引数が足りないことを検出できません。

8検査の対象を照合

正常な式、演算子の不正な並び、未閉鎖括弧を調べます。

[(text, brackets(text)[0], parse_status(text)) for text in [expression, '1 + * 2', '(1+2']]括弧検査と構文解析を比較

正常式だけが解析に成功します。1 + * 2は括弧検査TrueでもSyntaxErrorです。字句・括弧・構文はそれぞれ異なる条件を調べており、一つの検査が通っても全ての妥当性は保証されません。

まとめ

字句解析は数値や演算子へ分け、構文解析はそれらの関係を木にします。

演算の優先順位や括弧は木の親子関係へ反映されます。

括弧の対応はスタックで調べられますが、式全体の文法には別の解析が必要です。

操作履歴と解説を振り返れます。

Python 3

1
import re; expression = '12 + 3 * (4 - 1)'; tokens = re.findall(r'[0-9]+|[+*()-]', expression); tokens
['12', '+', '3', '*', '(', '4', '-', '1', ')']
2
import ast; tree = ast.parse(expression, mode='eval'); print(ast.dump(tree, indent=2))
Expression(
  body=BinOp(
    left=Constant(value=12),
    op=Add(),
    right=BinOp(
      left=Constant(value=3),
      op=Mult(),
      right=BinOp(
        left=Constant(value=4),
        op=Sub(),
        right=Constant(value=1)))))
3
type(tree.body.op).__name__, type(tree.body.right.op).__name__, type(tree.body.right.right.op).__name__, 12 + 3 * (4 - 1)
('Add', 'Mult', 'Sub', 21)
4
other = ast.parse('(12 + 3) * 4 - 1', mode='eval'); print(ast.dump(other, indent=2)); (12 + 3) * 4 - 1
Expression(
  body=BinOp(
    left=BinOp(
      left=BinOp(
        left=Constant(value=12),
        op=Add(),
        right=Constant(value=3)),
      op=Mult(),
      right=Constant(value=4)),
    op=Sub(),
    right=Constant(value=1)))
59
5
def brackets(text): stack, trace = [], [] for i, ch in enumerate(text): if ch == '(': stack.append(i) elif ch == ')': if not stack: return False, i, trace trace.append((stack.pop(), i)) return not stack, stack, trace
6
[(text, brackets(text)) for text in ['((1)+2)', '1)', '(1+2']]
[('((1)+2)', (True, [], [(1, 3), (0, 6)])), ('1)', (False, 1, [])), ('(1+2', (False, [0], []))]
7
def parse_status(text):
    try:
        ast.parse(text, mode='eval')
        return 'accepted'
    except SyntaxError as error:
        return type(error).__name__
8
[(text, brackets(text)[0], parse_status(text)) for text in [expression, '1 + * 2', '(1+2']]
[('12 + 3 * (4 - 1)', True, 'accepted'), ('1 + * 2', True, 'SyntaxError'), ('(1+2', False, 'SyntaxError')]
演習完了