微客导航 » 文章资讯 » 解释TOC中的左线性正则语法

解释TOC中的左线性正则语法

2023-06-07 16:36:02 469

正则文法描述了正则语言。它由四个部分组成，如下所示-

G = (N, E, P, S)

在哪里，

N-非终结符的有限集，

E-一个有限的终端符号集，

P-一组产生式规则，每一个都在形式中

S→aB

S→一个

S→∈，

S∈N是起始符号。

上述语法可以有两种形式-

右线性正则语法

左线性正则语法

线性语法

当语法部分的右侧只有一个终端时，它是线性的，否则是非线性的。

在左正则语法（也称为左线性语法）中，规则的形式如下-

L→a,{L是N中的非终结符，a是Σ中的终结符}

L→Ma，{L和M在N中，a在Σ}

L→∈，{∈是空串}。

左线性语法意味着非终结符将在左侧。

考虑一种语言{bⁿab^ma|n>=2，m>=2}

基于给定语言生成的左线性语法是-

S → Bbba       ⇒ last 3 symbols bba
B → Bb| Dbba   ⇒ for bm and bba are for bn followed by a.
D → Db|e       ⇒ for bn-2