左線性文法是一種特定的形式文法,其特點如下:
定義。左線性文法的每條規則都是左遞歸的,即規則的左側是一個非終結符,而右側是終結符或非終結符,且所有產生式的右部首符號都必須相同。
套用。左線性文法常用於描述程式語言中的詞法結構,例如,通過規則如A→Ba或A→a(其中A是非終結符,a是終結符)來定義標識符和關鍵字的識別規則。
與右線性文法的區別。左線性文法與右線性文法的主要區別在於推導的方向,在左線性文法中,推導是從左到右進行的,即在每個推導步驟中,非終結符被替換為右部的第一個符號。相對地,右線性文法的推導是從右到左進行的。
此外,值得注意的是,左線性文法和右線性文法都是正則文法的特例,正則文法是更廣泛的一類形式文法,包括左線性文法和右線性文法在內的所有正則文法都是上下文無關文法的一種形式。