第五章定義了規範中使用的句法和詞彙語法以及演算法,5.1 句法和詞彙語法章節包括上下文無關語法、詞彙和正則表達式語法、數字字串語法、句法語法、語法符號,5.2 演算法章節包括抽象操作、語法導向操作、運行時語義、靜態語義、數學運算、值表示法、識別。
上下文無關文法 (Context-Free Grammars)
上下文無關文法是規範中用來定義語言的一個文法形式,一個語句不需要考慮上下文的語意脈絡,只要符合文法規則就是一個有效的語句。以下是幾個文中提及的上下文無關文法的概念:
productions 產生式
包含了終結符和非終結符,用來定義符號間轉換的規則。產生式的左側為一個非終結符,右側為終結符及零到多個非終結符構成。產生式是構成文法的基本單位。
A -> b // A 為非終結符,b 為終結符,本產生式表達了 A 可轉換為 b 這個規則
nonterminal 非終結符
可轉換為其他符號的符號。
terminal 終結符
不可轉換為其他符號的符號。
Chain Production 鏈式產生式
指的是右側包含了一個非終結符及零到多個終結符構成,這樣的產生式能夠被簡化。
S -> A
A -> B
B -> C
C -> "hello"
// 上面的產生式能夠簡化為下列的產生式
S -> "hello"
Goal Symbol 目標符號
文法開始的非終結符,由此可推導出文法中的所有句子,是最根本的存在。
規範中對於上下文無關文法的說明十分簡略,但大致上足夠用來理解後續關於詞彙和正則表達式文法、數字字串文法、句法文法的推導。這些文法都是以上下文無關文法來定義,由一組產生式所構成。