编译原理之 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
  • 最后更新：2023年01月20日 - 01:01
  • 本文链接： https://xlui.me/t/compiling-principle-chomsky/
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处！