自拟一微小语言的上下文无关文法(包括表达式的产生式等),计算Vn符号的First()和Fol low()。
时间: 2024-10-24 15:07:24 浏览: 14
我们可以创建一个非常简单的自定义微小语言,例如用于描述算术表达式。这个语言可以包含数字、加号 (+) 和星号 (*)。上下文无关文法 (CFG) 可以表示如下:
```
S -> E | S '+' E | S '*' E
E -> N | '(', S ')'
N -> <digit> | '0' ('.' <digit>)* | '0.'
digit -> [1-9]
```
其中 `S` 表示整个表达式,`E` 表示基本元素(可能是数字或嵌套的表达式),`N` 表示数字。
现在我们来计算 `First()` 和 `Follow()`:
- `First(S)` 包含所有可能的开始符号 'S', '+', '*', '(' 和数字。
- `First(E)` 包含 'E', '+', '*', '(' 和数字。
- `First(N)` 包含数字字符 '0' 至 '9'。
- `Follow(S)` 通常在没有明确的右递归时,会包含非终结符表头的下一个符号,这里就是 ')',还有所有的运算符 '+' 和 '*'.
- `Follow(E)` 同理,需要添加 ')' 以及其后的运算符。
- `Follow(N)` 因为没有 'N' 的直接后续非终结符,所以 Follow('N') 就是空集。
让我们列出具体的 `First()` 和 `Follow()` 集合:
```markdown
First():
S: {'S', '+', '*', '(', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
E: {'E', '+', '*', '(', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
N: {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
Follow():
S: {')', '+', '*'}
E: {')', '+', '*'}
N: {}
```
阅读全文