勵志

勵志人生知識庫

什麼是3型文法

3型文法,也稱為正則文法,是一種特定的上下文無關文法。它有以下特點:

式子左邊只能有一個字元,並且這個字元必須是非終結符。

式子右邊最多有兩個字元,如果存在兩個字元,則必須是一個終結符和一個非終結符。如果只有一個字元,那麼這個字元必須是終結符。

式子右邊的格式必須一致。如果存在一個產生式是`(終結符+非終結符)`,那麼所有的產生式都必須遵循這個格式。如果存在一個產生式是`(非終結符+終結符)`,那麼所有的產生式都必須遵循這個格式。

正規文法包括左線性文法和右線性文法,這兩種文法都是3型文法。左線性文法要求式子右邊的產生式是`(非終結符+終結符)`的格式,而右線性文法要求式子右邊的產生式是`(終結符+非終結符)`的格式。