2022-CS310FZ-January
Q1
a) Give a regular expression for language L={w|w does not contain substring 011} on Σ = {0,1}.
拆解问题：找出允许和不允许的模式，根据不同情况分别构建，将它们组合起来。
一开始只考虑 0 开头，可以有无数个，但接下来的1要考虑数量
→ 转变为相当于考虑
00, 10 在中间可以重复无数次b) Eliminate left recursion for the following grammar
注意隐藏 indirect left recursion：
Q2
For a langeuage L={w|w start with 10 and end with 11} defined on Σ = {0,1}, complete the following tasks:
a) Give a regular expression for L.
b) Design an NFA for L.
表示选择和表示重复的时候需要带上 ε 进行转移（自动机可以在不消耗输入符号的情况下从一个状态转移到另一个状态）
c) Transform the NFA from (b) to a DFA.
I | I0 | I1 |
{0} | Ø | {1} |
{1} | {2,3,6} | Ø |
{2.3.6} | {3,4,5,6,8,9} | {3,4,6,7,8,9} |
{3,4,5,6,8,9} | {3,4,5,6,8,9} | {3,4,6,7,8,9,10} |
{3,4,6,7,8,9} | {3,4,6,7,8,9} | {3,4,6,7,8,9,10} |
{3,4,6,7,8,9,10} | {3,4,6,7,8,9} | {3,4,6,7,8,9,10,11} |
{3,4,6,7,8,9,10,11} | {3,4,6,7,8,9} | {3,4,6,7,8,9,10,11} |
State | 0 | 1 |
q0 | Ø | q1 |
q1 | q2 | Ø |
q2 | q3 | q4 |
q3 | q3 | q5 |
q4 | q3 | q5 |
q5 | q4 | q6 |
q6 | q4 | q6 |
Q3
Given the following grammar
a) For each production A → a，compute the First and Follow sets for A and a, respectively.
- First(E) = First(T) = {(, id}
- First(T) = First(F) = {(, id}
- First(E_R) = {+, ε}
- First(T_R) = {*, ε}
- First(F) = {(, id}
- Follow(E) = { $, ) }
- Follow(E_R) = Follow(E) = { $, ) }
- Follow(T) = First(E_R) / ε ∪
Follow(E)= { +, $, ) }
- Follow(T_R) = Follow(T) = { +, $, ) }
- Follow(F) = First(T_R) /ε + ∪
Follow(T)= { *, + , $, ) }
b) Does the grammar belong to LL(1)? Give a detailed reason for your answer?
Yes. Since the grammar does not have any First/First or First/Follow conflicts for any of its non-terminals, it satisfies the requirements for being an LL(1) grammar.
c) Use the computed First and Follows sets to construct a Predictive Parsing Table.
ㅤ | + | * | id | ( | ) | $ |
E | ㅤ | ㅤ | T E_R | T E_R | ㅤ | ㅤ |
E_R | + T E_R | ㅤ | ㅤ | ㅤ | ε | ε |
T | ㅤ | ㅤ | F T_R | F T_R | ㅤ | ㅤ |
T_R | ε | * F T_R | ㅤ | ㅤ | ε | ε |
F | ㅤ | ㅤ | id | ( E ) | ㅤ | ㅤ |
d) Demonstrate whether string “id*id+id)” belongs to the grammar in details.
It doesn’t belong to the grammar, since parentheses exist in pairs.
Q4
For the following grammar:
a) Construct an LR(0) Automaton
b) Is the grammar an example of a SLR parser? If so, construct its SLR-paring table; Otherwise, demonstrate the conflict in the construction of the table.
Follow(S) = { $ }，Follow(A) = { a, c }
No, it is not a SLR parser, since there are conflicts in cell [a, 7] and [c, 4].
Q5
For the following grammar:
a) Construct an LR(1) automaton
b) Construct an LR(1) paring table
c) Is G[S] an LR(1) grammar? Please give the reason for your answer.
Yes, since there are not any First/First or First/Follow conflicts based on the question (b) parsing table.
Review Notes
Syntax vs. Semantics
- Syntax refers to the formal structure and rules for arranging symbols in a language.
- Semantics deals with the meaning and behavior of these syntactical constructs.
Lexical Specification → Regex in five steps
- Write a regex for each token
- Number = digit
- Keyword = ‘if’ + ‘else’
- Identifier = letter (letter digit)*
- OpenPar = ‘(’
- Construct R matching all lexemes for all t okens
- R = Keyword + Identifier Number + … = R1 + R2 + …
- 将上一步定义的所有正则表达式合并成一个大的正则表达式，每个单元之间用 “+”（
|）连接。
- Let input be X1 … Xn
- For 1 = i = n check X1 … Xn ∈ L(R)
- 把要分析的代码看作一串字符，从头到尾依次是 X1, X2, ..., Xn
- If success, then we know that X1 …X i ∈ L(Rj) for some j
- 用步骤 2 中的大正则表达式来匹配输入字符串的开始部分。如果匹配成功，那么这部分字符串就是某个词法单元。
- Remove X1 …Xi from input and go to (3)
- 把已经匹配成功的部分从输入字符串中去掉，然后重复这个过程，直到整个字符串被分解完毕。
Context-Free Grammars advantages
- They provide a clear and formal way to describe the syntactic structure.
- They are capable of expressing a wide range of language.
- They facilitate the creation of efficient parsing algorithm.