编译原理之 Chomsky 文法的判断 —— Java 实现

文法的定义和记号

$$ G = (V_N, V_T, P, S) \qquad (V_N \cap V_T = \varnothing, V_N \cup V_T = V) $$

是 N.Chomsky 在 1956 年描述形式语言时首先给出的。同时,Chomsky 还对产生式的形式给以不同的限制而定义了四类基本的文法,分别称之为 0 型文法,1 型文法,2 型文法和 3 型文法。

明确定义

  • 0 型文法:对任一产生式 $\alpha \to \beta$,都有 $\alpha \in V^+, \quad \beta \in V^*$
  • 1 型文法:对任一产生式 $\alpha \to \beta$,都有 $\mid\beta\mid \ge \mid\alpha\mid, \quad \alpha,\beta \in V^+$,仅仅 $\alpha \to \epsilon$ 除外
  • 2 型文法:对任一产生式 $A \to \beta$,都有 $A \in V_N, \quad \beta \in V^+$
  • 3 型文法:任一产生式都形如 $A \to Ba$ 或 $A \to a$,其中 $A,B \in V_N, \quad a \in V_T$,该文法称为右线性文法。类似可定义左线性文法。

判断思路

0 型文法

  • 字符串 $\alpha$ 的范围是 $V^+$,是全符号集的一个正闭包,即符号集中所有符号的任意组合,且不包含 $\epsilon$ 元素

  • 字符串 $\beta$ 的范围是 $V^*$,是全符号集的自反传递闭包,也即 $V^+ \cup {\epsilon}$

  • 要判断一个文法是否是 0 型文法,只需要判断左侧非空且不全为小写即可

  • 任何 0 型语言都是递归可枚举的,故 0 型语言又称递归可枚举集

1 型文法

  • 首先 1 型文法必须是 0 型文法

  • 1 型文法除了 $\alpha \to \epsilon$ 这个特例外,其他情况都满足 $\beta$ 的长度大于 $\alpha$ 的长度

  • 1 型文法也叫上下文相关(敏感)文法

2 型文法

  • 首先 2 型文法必须是 1 型文法

  • 2 型文法左侧必须是一个非终结符

  • 2 型文法也叫上下文无关文法

3 型文法

  • 首先 3 型文法必须是 2 型文法

  • 3 型文法必须满足以下两种形式之一

  1. $A \to aB$ 或 $A \to a$
  2. $A \to Ba$ 或 $A \to a$
  • 3 型文法也叫正规文法

代码实现

保存产生式集

可以使用 List 来保存所有产生式,用内部类来表示具体的产生式:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Chomsky {
private List<Producer> producers = new ArrayList<>();

private static final class Producer {
String left;
String right;

public Producer(String left, String right) {
this.left = left;
this.right = right;
}
}
}

判断 0 型文法

遍历产生式集,如果有一个产生式不符合条件,则直接退出。

1
2
3
4
5
6
7
8
9
public boolean isZero() {
for (Producer producer : producers) {
if (producer.left.length() == 0 || producer.left.equals(producer.left.toLowerCase())) {
// 判断产生式的左部是否为空或者全部是小写,如果是则不是 0 型文法
return false;
}
}
return true;
}

关于判断左部是否全为小写,使用 String.toLowerCase() 将其转换为小写后再与原产生式比较,相等则原产生式为小写。

判断 1 型文法

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isFirst() {
if (isZero()) {
for (Producer producer : producers) {
if (producer.right.length() != 0 && producer.right.length() < producer.left.length()) {
// 1 型文法必须右部长度大于左部,除了右部为ε的情况
return false;
}
}
return true;
} else {
return false;
}
}

1 型文法必须先是 0 型文法。

1 型文法的判断跳过了右部为 $\epsilon$ 的情况,即允许右部为 $\epsilon$。

判断 2 型文法

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isSecond() {
if (isFirst()) {
for (Producer producer : producers) {
if (producer.left.length() != 1 || producer.left.matches("[a-z]")) {
// 2 型文法左部必须为 1,且左部为 1 时不能为非终结符
return false;
}
}
return true;
} else {
return false;
}
}

2 型文法必须先是 1 型文法。

首先限制左部长度必须为 1,然后利用正则判断是否为小写,[a-z] 匹配一个小写字符。

判断 3 型文法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isThird() {
if (isSecond()) {
int countLeft = 0, countRight = 0;
for (Producer producer : producers) {
if (producer.right.matches("[A-Z]?[a-z]")) {
countLeft++;
}
if (producer.right.matches("[a-z][A-Z]?")) {
countRight++;
}
}
if (countLeft == producers.size()) {
System.out.println("此文法是 3 型文法,并且是左线性文法!");
return true;
}
if (countRight == producers.size()) {
System.out.println("此文法是 3 型文法,并且是右线性文法!");
return true;
}
}
return false;
}

3 型文法必须先是 2 型文法。

全部源代码

Chomsky.java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.*;

public class Chomsky {
private List<Producer> producers = new ArrayList<>();

public void add(Producer producer) {
producers.add(producer);
}

public boolean isZero() {
for (Producer producer : producers) {
if (producer.left.length() == 0 || producer.left.equals(producer.left.toLowerCase())) {
// 判断产生式的左部是否为空或者全部是小写,如果是则不是 0 型文法
return false;
}
}
return true;
}

public boolean isFirst() {
if (isZero()) {
for (Producer producer : producers) {
if (producer.right.length() != 0 && producer.right.length() < producer.left.length()) {
// 1 型文法必须右部长度大于左部,除了右部为ε的情况
return false;
}
}
return true;
} else {
return false;
}
}

public boolean isSecond() {
if (isFirst()) {
for (Producer producer : producers) {
if (producer.left.length() != 1 || producer.left.matches("[a-z]")) {
// 2 型文法左部必须为 1,且左部为 1 时不能为非终结符
return false;
}
}
return true;
} else {
return false;
}
}

public boolean isThird() {
if (isSecond()) {
int countLeft = 0, countRight = 0;
for (Producer producer : producers) {
if (producer.right.matches("[A-Z]?[a-z]")) {
countLeft++;
}
if (producer.right.matches("[a-z][A-Z]?")) {
countRight++;
}
}
if (countLeft == producers.size()) {
System.out.println("此文法是 3 型文法,并且是左线性文法!");
return true;
}
if (countRight == producers.size()) {
System.out.println("此文法是 3 型文法,并且是右线性文法!");
return true;
}
}
return false;
}

/**
* 判断文法的具体类型,从 3 到 0 逐步判断
*/
public void test() {
if (!isThird()) {
if (isSecond()) {
System.out.println("此文法是 2 型文法");
} else if (isFirst()) {
System.out.println("此文法是 1 型文法");
} else if (isZero()) {
System.out.println("此文法是 0 型文法");
} else {
System.out.println("此文法不是 0 型文法!");
}
}
}

private static final class Producer {
String left;
String right;

public Producer(String left, String right) {
this.left = left;
this.right = right;
}
}

public static void main(String[] args) {
int count;
String[] input;
Scanner scanner = new Scanner(System.in);
Chomsky chomsky = new Chomsky();

System.out.println("请输入产生式的个数:");
count = scanner.nextInt();
System.out.println("请依次输入产生式(示例:A->ab,一行一个):");
for (int i = 0; i < count; i++) {
input = scanner.next().split("->");
try {
chomsky.add(new Producer(input[0], input[1]));
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("输入非法,请重新运行程序!!!");
System.exit(1);
}
}

chomsky.test();

scanner.close();
}
}
-------------本文结束感谢阅读-------------
  • 本文标题:编译原理之 Chomsky 文法的判断 —— Java 实现
  • 本文作者:xlui
  • 发布时间:2018年04月10日 - 16:04
  • 最后更新:2018年07月29日 - 19:07
  • 本文链接: https://xlui.me/t/chomsky/
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!