文法(『コンピュータシステムの理論と実装』10.1.2)
10.1.2 文法
前提として字句解析して、プログラムはトークンになっている
変数宣言、文、式などのような言語構造へトークンをグループ化する方法
このグループ化および識別作業は、文法(grammar)として知られるルール(あらかじめ定義されたルール)をトークンに適合させることによって実現できる
ほとんどすべてのプログラミング言語は、文脈自由文法(context-free grammar)として知られる定式化によって定義することができる。
文脈自由文法は、ある言語の構文要素がより単純な要素からどのように構成されるか、ということを指定したルールの集合である。
「ある言語の構文要素がより単純な要素からどのように構成されるか」に関わる用語
終端要素=トークン
ターミナルとも呼ばれる
例:while文を構成するキーワード
非終端要素:より高水準な構文要素
例:whileなどのトークンから構成されたwhile文
文法はふたつの視点から見ることができる
終端要素をより高水準な構文要素へ組み合わせる
宣言を行う視点
例:whileなどのトークンからwhile文が書ける
与えられた入力(トークン集合)を非終端要素へ、そして終端要素へとパースを行う
分析を行う視点
例:トークン集合の中の、while文の構成要素をパース
一般的な文法のルールは再帰構造をしており
再帰構造が、機械がプログラムの構造を理解できるポイントだと思う
再帰的な定義によって、セミコロンで分離された文に――(略)、そして、任意の数だけ分離される場合であっても――適合することができる
Pythonのif文のBNFを見て感じた体験に近い