正则表达式和上下文无关语法的区别

语法表示自然语言会话的句法规则。计算机科学在很大程度上使用了形式语言的理论。 1956 年，诺姆·乔姆斯基 (Noam Chomsky) 给出了编写计算机语言的语法数学模型。当可以从文法中导出所有字符串的集合时，就说语言是从该文法中生成的。两种类型的语法是常规语法和上下文无关语法。任何可以用正则表达式描述的语言都是正则语言。上下文无关文法是正则表达式的概括。可以使用正则表达式来编写正则语言和上下文无关文法来编写上下文无关文法。

正则表达式，上下文无关语法

什么是正则表达式

正则文法生成正则语言。该文法的左侧有一个非终结符，右侧由一个终结符或单个终结符后跟一个非终结符组成。它可以有如下产生式规则。

X -> a 或 X -> a Y

其中 X, Y ϵ N（非终端）和一个 ϵ T（终端）

正则表达式有助于编写正则文法来描述正则语言。

正则表达式以代数方式表示一组特定的字符串。编写正则表达式时要遵循的一些重要规则如下。

终结符、空符号和空符号是正则表达式。
两个正则表达式的并集是一个正则表达式。
两个正则表达式的串联就是一个正则表达式。
迭代或闭包是一个正则表达式。

集合 {0, 1, 2} 的正则表达式如下。

R = 0 + 1+2

集合 {abb, a, b, bba} 可以用下面的正则表达式表示。

R = abb + a +b + bba

考虑集合 {ϵ, 0, 00, 000,…}

ϵ 是空字符串。正则表达式为 R = 0*。这表示包括空符号在内的符号的关闭。

在集合 {1, 11, 111, 1111,…..}

正则表达式为 R = 1 ^+. 这个 + 表示一个符号的关闭，不包括空符号。

什么是上下文无关语法

在形式语言理论中，Context Free Language (CFL) 是一种由 Context Free Grammar 生成的语言。四个参数定义上下文无关文法 (G)。

G= {V, ∑, S, P}

V：一组变量或非终结符。

∑：终结符集

S：开始符号

P：生产规则

上下文无关语法的产生式规则格式如下。

A -> a 其中 a = {V, ∑ }* 和 A ϵ V

上下文无关语法的一个示例如下。每个产生式由一个非终结符和一个正则表达式组成。

对于生成相同数量的 a 和 b 的语言，格式为 a乙.上下文无关文法如下。

G = {(S, A), (a, b), (S ->aAb, A -> aAb | ϵ)}

考虑到开始符号，

S – > a a b

通过应用 A -> aAb

→ a a b b

通过再次应用 A -> aAb，

→ a a a A b b b

通过应用 A -> ϵ （这个符号表示一个空字符串）

→ a a b b b

→ 一个 ³ 乙 ³

在考虑输出时，a 的数量等于 b 的数量。它有一个乙形式。

正则表达式与上下文无关语法的关系

正则表达式和上下文无关语法的区别

定义

正则表达式是形式语言理论中的一个概念，它是定义搜索模式的字符序列。 Context Free Grammar 是形式语言理论中的一种形式语法，它是一组产生式规则，用于描述给定形式语言中所有可能的字符串。

用法

正则表达式有助于以代数方式表示某些字符串集。它有助于表示常规语言。上下文无关文法有助于定义上下文无关语言的所有可能字符串。

结论

正则表达式是一种模式匹配方法。它是一种灵活的方法，可以提供一种灵活而简洁的方式来匹配文本字符串。它定义了常规语言中的所有字符串。另一方面，上下文无关文法允许定义属于上下文无关语言的所有字符串。正则表达式和上下文无关文法的区别在于，正则表达式有助于描述正则语言的所有字符串，而上下文无关文法则有助于定义上下文无关语言的所有可能的字符串。