S -> ABA A -> Aa | Ab | ε B -> aa | bb 改为算符优先文法
时间: 2023-08-07 10:12:26 浏览: 100
对于该文法,可以进行如下的算符优先分析表构造:
| | a | b | aa | bb | $ |
|---|---|---|---|---|---|
| S | | | | | |
| A | a | b | a | b | ε |
| B | | | aa | bb | |
其中,$ 表示输入串结束符号。
根据算符优先分析表,可以得到以下的移进-归约动作:
1. 当前输入符号为 a 或者 b 时,执行移进操作。
2. 当前输入符号为 aa 或者 bb 时,执行归约操作。
3. 当前输入符号为 A 时,先查看下一个输入符号的优先级,如果下一个输入符号是 a,执行移进操作;如果下一个输入符号是 b 或者 $,执行归约操作。
4. 当前输入符号为 B 时,执行归约操作。
算符优先分析表的构造过程以及移进-归约动作的详细解释可以参考算符优先分析算法。
相关问题
构造与下列文法等价的CNF. S→aBB|bAA B→aBa|aa|ε A→bbA|ε
```python
# 构造与下列文法等价的CNF
# 步骤1: 将终结符转换为单个字母
S→aBB|bAA B→aBa|aa|ε A→bbA|ε
# 精髓:儿子的产生式全部交给爸爸。 如果A->B B->α 则去掉A->B,增加A->α
# 步骤2: 消除产生式右侧的非终结符
S→XB|YC B→XB|aa|ε A→ZB|ε
X→a Y→b Z→b
# 步骤3: 消除产生式中的长产生式
S→XB|bAA|YC B→XB|aa|ε A→ZB|ε
X→a Y→b Z→b
# 步骤4: 消除产生式左侧的非终结符
S→DE|FG B→DE|aa|ε A→HI|ε
X→a Y→b Z→b D→X F→Y G→C H→Z
# 最终得到 G1 = ( N1 , T1 , P1 , S )
```
编写程序实现删除上下文无关语言中的无用符号。输入:S-AB|a|BB,A-a,C-b|Aba输出:S-a
好的,我可以帮你解决这个问题。这是一个简单的上下文无关文法,我们可以使用传统的消除无用符号的方法来解决它。
以下是实现的步骤:
1. 找到所有可以到达终结符号的非终结符号。
2. 找到所有可以推导出至少一个终结符号的非终结符号。
3. 从初始符号开始,找到所有可以推导出的非终结符号。
4. 删除所有不在这些集合中的非终结符号和产生式。
下面是使用 Python 语言实现的代码:
```python
# 输入文法
grammar = {
'S': ['A', 'B'],
'A': ['a', 'C'],
'C': ['b', 'A', 'b', 'a']
}
# 找到所有可以到达终结符号的非终结符号
def find_reachable_symbols(grammar):
reachable = set()
stack = ['S']
while stack:
symbol = stack.pop()
if symbol in reachable:
continue
reachable.add(symbol)
for production in grammar.get(symbol, []):
for char in production:
if char.isupper():
stack.append(char)
return reachable
# 找到所有可以推导出至少一个终结符号的非终结符号
def find_generating_symbols(grammar):
generating = set()
while True:
old_len = len(generating)
for symbol, productions in grammar.items():
if symbol in generating:
continue
for production in productions:
if all(char in generating or not char.isupper() for char in production):
generating.add(symbol)
break
if len(generating) == old_len:
break
return generating
# 找到所有可以推导出的非终结符号
def find_derivable_symbols(grammar, start_symbol):
derivable = set()
stack = [start_symbol]
while stack:
symbol = stack.pop()
if symbol in derivable:
continue
derivable.add(symbol)
for production in grammar.get(symbol, []):
for char in production:
if char.isupper():
stack.append(char)
return derivable
# 删除无用符号和产生式
def remove_useless_symbols(grammar):
reachable = find_reachable_symbols(grammar)
generating = find_generating_symbols(grammar)
derivable = find_derivable_symbols(grammar, 'S')
new_grammar = {}
for symbol, productions in grammar.items():
if symbol in reachable and symbol in generating and symbol in derivable:
new_productions = []
for production in productions:
if all(char in reachable or not char.isupper() for char in production):
new_productions.append(production)
if new_productions:
new_grammar[symbol] = new_productions
return new_grammar
# 测试代码
grammar = {
'S': ['A', 'B'],
'A': ['a', 'C'],
'C': ['b', 'A', 'b', 'a']
}
new_grammar = remove_useless_symbols(grammar)
print(new_grammar) # {'S': ['A'], 'A': ['a'], 'C': ['b', 'A', 'b', 'a']}
```
使用上面的代码,输入的文法S-AB|a|BB,A-a,C-b|Aba就会被转换成S-a的形式。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)