トップ言語処理入門 > BNFおよび拡張BNF

BNFおよび拡張BNF

1.BNF

字句規則や構文規則は BNF記法で表現されることが多い。

BNF(Backus Naur FormまたはBackus Normal Form)とは、 プログラミング言語の構文を定義するのに用いられるメタ言語(言語を定義するための言語)である。 Backusによって提案され、NaurがALGOL 60 の文法定義に用いた。

現在では、BNFを拡張した様々な拡張BNFが広く用いられ、 プログラミング言語の定義だけでなく、 HTMLやXMLの構文定義、通信プロトコルの定義など幅広い分野で利用されている。

1.1 四則演算の定義

算術演算の規則はBNFでは次のように表現できる。 ここで、加減乗除演算子は+、−、*、/で表している。 この規則では( )内が先に計算され、*、/が+、−より優先順位が高いことを 正確に反映している。

  <Expr> ::= <Term> | <Expr> + <Term> | <Expr> − <Term> 
  <Term> ::= <Fact> | <Term> * <Fact> | <Term> / <Fact> 
  <Fact> ::= (<Expr>) | 数値 

ここで、::=| はメタ言語の記号であり、+、−、*、/ は四則演算の演算子である。 このような書き方では、両者の違いが分かりにくいし、 定義する言語にメタ言語の記号 | を演算子として持つ場合、表現できない。 そのため、定義する言語の演算子は例えば '+' のように、引用符で括るなどの記述方法が使われる。 また、定義する言語に現れる予約語(C言語で言えば、int、forなど)も引用符で括る。 そうすれば、メタ変数は < > で括らなくても、予約語と区別できる。 すなわち、この場合、四則演算の構文規則は次のように表される。

  Expr ::= Term | Expr '+' Term | Expr '-' Term 
  Term ::= Fact | Term '*' Fact | Term '/' Fact 
  Fact ::= '(' Expr ')' | 数値 

( )はメタ言語の記号としても使われるが、上の構文規則での ( ) はメタ言語の記号ではなく、 引用符で括られていることから四則演算での記号であることが分かる。 因みに、プログラミング言語の世界では、このような ( ) も演算子と呼ばれる。

ここで 数値 はメタ変数でも予約語でもないが、 終端記号と同様に、BNFではこれ以上詳しく定義しないものである。 英字では例えば NUMBER と書き、メタ変数ではないことが一目で分かるような書き方をする。

2.BNF記法および拡張BNF記法の実例

BNF記法あるいは拡張BNF記法のいくつかの実例を挙げておく。 ここで、ひとつひとつを詳しく理解する必要はない。類似の構文規則を設計するときに参考にすればよい。

2.1 mcfromc(C言語サブセット)

mcfromc(C言語プログラムを単調型制約システムに変換する) ではC言語のサブセットをBNF記法でつぎのように記述している。 大文字で記述されたIDENTIFIER、CONSTANTは終端記号と同様にBNF記法ではこれ以上詳しく説明しない。 IDENTIFIERは変数名や関数名など、CONSTANTは数値 2, 3.13、文字 'a', '1' 、文字列 "123"、"abc" などを表す。

IDENTIFIERやCONSTANTにも約束事があり、それぞれを BNF記法で表現することも可能であるが、 約束事を文章で表した方が分かりやすい場合、この例のように、 その部分(字句解析に当たる)にはBNF記法は使わないことも多い。 つまり、構文規則のみBNF記法で表現し、字句規則および意味規則は別途文章で記述する。
The Grammar in BNF

translation_unit ::= external_declaration 

external_declaration ::= function_definition | declaration 

function_definition ::= declaration_specifiers declarator declaration_list compound_statement 
    | declaration_specifiers declarator compound_statement 
    | declarator declaration_list compound_statement | declarator compound_statement 

primary_expression ::= IDENTIFIER | CONSTANT | '(' expression ')' 

postfix_expression ::= primary_expression | postfix_expression '++' | postfix_expression '--' 

unary_expression   ::= postfix_expression | '++' unary_expression | '--' unary_expression 
    | unary_operator unary_expression 

unary_operator  ::= '+' | '-' 

multiplicative_expression  ::= unary_expression | multiplicative_expression '*' unary_expression
    | multiplicative_expression '/' unary_expression 
    | multiplicative_expression '%' unary_expression 

additive_expression  ::= multiplicative_expression 
    | additive_expression '+' multiplicative_expression 
    | additive_expression '-' multiplicative_expression 

shift_expression  ::= additive_expression 

relational_expression  ::= shift_expression | relational_expression '<' shift_expression 
    | relational_expression '>' shift_expression | relational_expression '<=' shift_expression 
    | relational_expression '>=' shift_expression 

equality_expression  ::= relational_expression | equality_expression '==' relational_expression 
    | equality_expression '!=' relational_expression 

and_expression  ::= equality_expression 

exclusive_or_expression ::= and_expression 

inclusive_or_expression ::= exclusive_or_expression 

logical_and_expression  ::= inclusive_or_expression 
    | logical_and_expression '&&' inclusive_or_expression 

logical_or_expression   ::= logical_and_expression 
    | logical_or_expression '||' logical_and_expression 

conditional_expression  ::= logical_or_expression 

assignment_expression  ::= conditional_expression 
    | unary_expression assignment_operator assignment_expression 

assignment_operator  ::= '=' | '=' | '/=' | '+=' | '-=' | '%=' 

expression  ::= assignment_expression | expression ',' assignment_expression 

declaration  ::= declaration_specifiers ';' 
    | declaration_specifiers init_declarator_list ';' 

declaration_specifiers  ::= type_specifier 

init_declarator_list  ::= init_declarator | init_declarator_list ',' init_declarator 

init_declarator  ::= declarator | declarator '=' initializer 

type_specifier  ::= 'int' 

declarator  ::= direct_declarator 

direct_declarator  ::= IDENTIFIER | '(' declarator ')' 
    | direct_declarator '(' parameter_type_list ')' 
    | direct_declarator '(' identifier_list ')' | direct_declarator '(' ')' 

parameter_type_list  ::= parameter_list 

parameter_list ::= parameter_declaration | parameter_list ',' parameter_declaration 

parameter_declaration ::= declaration_specifiers declarator | declaration_specifiers 

identifier_list  ::= IDENTIFIER | identifier_list ',' IDENTIFIER 

initializer  ::= assignment_expression 
    | '{' initializer_list '}' | '{' initializer_list ',' '}' 

initializer_list  ::= initializer | initializer_list ',' initializer 

statement  ::= compound_statement | expression_statement 
    | selection_statement | iteration_statement 

compound_statement  ::= '{' '}' | '{' statement_list '}' | '{' declaration_list '}' 
    | '{' declaration_list statement_list '}' 

declaration_list  ::= declaration | declaration_list declaration 

statement_list  ::= statement | statement_list statement 

expression_statement  ::= ';' | expression ';' 

selection_statement  ::= 'if' '(' expression ')' statement 
    | 'if' '(' expression ')' statement 'else' statement 

iteration_statement  ::= 'while' '(' expression ')' statement 
    | 'do' statement 'while' '(' expression ')' ';' 
    | 'for' '(' expression_statement expression_statement expression ')' statement 

2.2 ECMAScript(JavaScript)の字句規則・構文規則

ECMAScript(JavaScript) (日本語訳) の字句規則・構文規則は拡張BNF記法で記述されている。 全体は膨大な量になるため、詳細は省略する。興味があれば、上のリンクをクリックしていただきたい。

ここでは、下に示すような記法が採用されている。 メタ変数(非終端記号)はイタリック体で記述し、 演算子や予約語(下図では全て演算子)は太字で記述している。 演算子や予約語を引用符で括らないので、すっきりしていて読みやすい。 このように、文字や記号の種別を書体で区別する方法もよくとられる。

ECMAScriptの拡張BNFには BNF の 「|」に当たる記号はない。 規則ごとに改行している。つまり、改行が BNF の 「|」に相当する。


右辺で末尾にサフィックスoptが付いたメタ変数は省略可能であることを表す。

Block :
    { StatementListopt }

二つ以上の中からいずれか一つというときには、次のように one of が使われる。

AssignmentOperator : one of
    *= /= %= += -= <<= >>= >>>= &= ^= |=