作りながら学ぶパーサジェネレータ入門 1

はじめに

第1回目の今回は「言語」と「文法」という用語について取り扱います。どちらも非常に意味の広い言葉で、文脈によって定義もさまざまです。説明が長くなるのでそのような意味の部分にはあまり深入りすることはせず、コンパイラ・インタプリタ・パーサジェネレータといった「言語処理系」と言われる分野においてどのような意味で使われているのかについて見ていきましょう。

言語

言語処理系では、「言語」という用語は基本的に「形式言語」を指します。簡単な定義としては定められた形式的なルールに従って生成される文字列の集合を意味します。日本語や英語などの「自然言語」と異なって明確な定義が可能で、ある文字列がその言語に属するかどうかを機械的に判別可能です。

例えば、英語のサブセットとして「基本5文型に含まれる1文のみ」「文中に修飾語を含まない」「文中の各構成要素は、1単語のみによって構成される」という言語を考えてみましょう。下記のような例が含まれます。

• It depends. (第1文型)
• This tastes good. (第2文型)
• Everyone calls it "Language." (第5文型)

逆に、英語でも下記のような例はこの言語には含まれません。

• She drives a car. (第3文型だが、目的語が2単語で構成されている)
• Looks good to me. (主語がなく、基本5文型に含まれない)
• It is very beautiful. (第2文型だが、修飾語 very が含まれる)

また、形式文法では文字列の内容や意味については言及していません。したがって、下記のような例はこの言語に含まれます。

• Fish flies. (第1文型だが、普通魚は空を飛ばない)
• Red is green. (第2文型だが、赤と緑は異なる色なので意味が通らない)

文法

「文法」という用語も「言語」と同様に、基本的に「形式文法」を指します。簡単な定義としてはある言語を定めるための形式的なルールの集合を意味します。文法に現れる1つ1つのルールのことを規則または生成規則と呼びます。

上の例で挙げた英語のサブセットの文法は、例えば下記のような規則に従った「文」の集合として定義される言語になります。

• 文は以下のいずれかの形を取り、ピリオドで終わる
  • 主語 + 動詞 (第1文型)
  • 主語 + 動詞 + 補語 (第2文型)
  • 主語 + 動詞 + 目的語 (第3文型)
  • 主語 + 動詞 + 目的語 + 補語 (第4文型)
  • 主語 + 動詞 + 目的語1 + 目的語2 (第5文型)
• 主語は1単語で構成される
• 動詞は1単語で構成される
• 補語は1単語で構成される
• 目的語は1単語で構成される
• 単語は英語の単語である

このような「αはA、B、C、...の要素がこの順番で並ぶ形で構成される」という規則からなる文法を文脈自由文法 (Context-Free Grammar, CFG) と呼び、文脈自由文法を使って定義される言語を文脈自由言語 (Context-Free Language, CFL) と呼びます。多くのプログラミング言語の文法は文脈自由文法で定義されており、このドキュメントで作成するパーサジェネレータも文脈自由文法を扱います。

バッカス・ナウア記法 (BNF)

文脈自由文法を表現するための記法として、バッカス・ナウア記法 (Backus-Naur Form, BNF) がよく使われます。BNFは、文法の規則を表現するための形式的な記法で、以下のような構文を持ちます。

<規則名> ::= <規則の構成要素>

::= の左辺は規則名、右辺はその規則がどのような構成要素からなるかを表します。構成要素は、他の規則名や文字列、またはそれらの組み合わせで表現されます。 例えば、先ほどの英語のサブセットの文法をBNFで表現すると、以下のようになります。

<文> ::= <主語> <動詞> "."
<文> ::= <主語> <動詞> <補語> "."
<文> ::= <主語> <動詞> <目的語> "."
<文> ::= <主語> <動詞> <目的語> <補語> "."
<文> ::= <主語> <動詞> <目的語> <目的語> "."
<主語> ::= <単語>
<動詞> ::= <単語>
<補語> ::= <単語>
<目的語> ::= <単語>

このうち、文法中に <規則名> としてあらわれる要素を非終端記号 (non-terminal symbol) と呼び、文字列としてあらわれる要素を終端記号 (terminal symbol) と呼びます。

実践

この章の実践として、パーサジェネレータの雛形を作成し、BNF の要領で文法を記述できるようにしましょう。前回に記載したとおり、扱う言語は「非負整数」とします。

まず、非負整数の文法を考えてみましょう。非負整数は、0 以上の整数であり、桁数に制限はありません。文字列としては、0 から 9 までの数字が、1つ以上の任意の数だけ並んだものと考えることができます。つまり、非負整数を表現する文法は、数字の列で構成されると定義できます。

<非負整数> ::= <数字列>

BNFでは、正規表現のような * や + のような繰り返しを表現することはできません。代わりに、規則の構成要素として規則自身を再帰的に呼び出すことで、繰り返しを表現します。具体的に言い換えれば「もともと数字の列であるものの後ろに数字を追加したものも数字の列である」ということを規則として定義します。数字列は1つ以上の数字から構成されるので、数字列は数字であるか、または数字列の後ろに数字が続く、と定義できます。

<数字列> ::= <数字>
<数字列> ::= <数字列> <数字>

最後に、数字を定義します。数字は0から9までの1文字なので、以下のように定義できます。

<数字> ::= "0"
<数字> ::= "1"
<数字> ::= "2"
<数字> ::= "3"
<数字> ::= "4"
<数字> ::= "5"
<数字> ::= "6"
<数字> ::= "7"
<数字> ::= "8"
<数字> ::= "9"

それでは、この文法を Ruby で表現するクラスを作成してみましょう。まずは、言語と文法の基本的な構造を定義します。まず、規則を表現するクラスを作成します。今回は入力を確認できるように、 to_s メソッドも実装します。

# rule.rb
class Rule
  def initialize(name, elements)
    @name = name
    @elements = elements
  end

  def to_s
    "#{@name} ::= #{@elements.join(' ')}"
  end
end

name には規則名となる非終端記号、elements には規則の構成要素を配列で渡します。簡単のため、非終端記号はシンボル、終端記号は文字列として渡されるものとします。

次に、文法を表現するクラスを作成します。 initialize メソッドで規則の配列を定義し、文法を構築します。

# grammar.rb
require './rule'

class Grammar
  attr_reader :rules

  def initialize
    @rules = []
    @rules << Rule.new(:non_negative_integer, [:digits])
    @rules << Rule.new(:digits, [:digit])
    @rules << Rule.new(:digits, [:digits, :digit])
    (0..9).each do |i|
      @rules << Rule.new(:digit, ["#{i}"])
    end
  end
end

最後に、パーサジェネレータの雛形を作成します。今回はまだ生成部分の実装は行いませんが、文法を出力するメソッドを追加しておきます。

# parser_generator.rb
require './grammar'

class ParserGenerator
  def initialize(grammar)
    @grammar = grammar
  end

  def generate
    @grammar.rules.each do |rule|
      puts rule.to_s
    end
  end
end

これで、パーサジェネレータの雛形が完成しました。実際に文法を出力してみましょう。

$ irb
irb(main):001> require './parser_generator'
=> true
irb(main):002> ParserGenerator.new(Grammar.new).generate
non_negative_integer ::= digits
digits ::= digit
digits ::= digits digit
digit ::= 0
digit ::= 1
digit ::= 2
digit ::= 3
digit ::= 4
digit ::= 5
digit ::= 6
digit ::= 7
digit ::= 8
digit ::= 9
=>
[#<Rule:0x000076ae645fee28 @elements=[:digits], @name=:non_negative_integer>,
 #<Rule:0x000076ae645fed88 @elements=[:digit], @name=:digits>,
 #<Rule:0x000076ae645fed10 @elements=[:digits, :digit], @name=:digits>,
 #<Rule:0x000076ae645fec70 @elements=["0"], @name=:digit>,
 #<Rule:0x000076ae645febf8 @elements=["1"], @name=:digit>,
 #<Rule:0x000076ae645feb80 @elements=["2"], @name=:digit>,
 #<Rule:0x000076ae645feb08 @elements=["3"], @name=:digit>,
 #<Rule:0x000076ae645fea90 @elements=["4"], @name=:digit>,
 #<Rule:0x000076ae645fea18 @elements=["5"], @name=:digit>,
 #<Rule:0x000076ae645fe9a0 @elements=["6"], @name=:digit>,
 #<Rule:0x000076ae645fe928 @elements=["7"], @name=:digit>,
 #<Rule:0x000076ae645fe8b0 @elements=["8"], @name=:digit>,
 #<Rule:0x000076ae645fe838 @elements=["9"], @name=:digit>]
irb(main):003>

よさそうです！
次回は、この文法を使ってパーサのもととなるオートマトンを生成する部分を実装していきます。

まとめ

今回は、「言語」と「文法」という用語について、言語処理系における意味を小さな例を取りつつ確認しました。
また、この文書を通して作成するパーサジェネレータの題材として非負整数を表現する文法を考え、それを Ruby で表現するクラスを作成しました。

練習問題

1. 今回定義した非負整数の文法に、負の整数を表現するための規則を追加してください。負の整数は、先頭にマイナス記号 - がつくことを考慮してください。
2. 今回定義した非負整数の文法に、浮動小数点数を表現するための規則を追加してください。浮動小数点数は、整数部と小数部があり、小数部は . の後に1つ以上の数字が続くことを考慮してください。
3. [発展] 今回定義した非負整数の文法は、日常生活で使われる非負整数の表現と一部異なる部分があります。それはどこでしょうか。わかったら、そのケースを考慮した文法を追加してください。