25 |
25 |
26 In case they can, give the corresponding token sequences. (Hint: |
26 In case they can, give the corresponding token sequences. (Hint: |
27 Observe the maximal munch rule and priorities of your regular |
27 Observe the maximal munch rule and priorities of your regular |
28 expressions that make the process of lexing unambiguous.) |
28 expressions that make the process of lexing unambiguous.) |
29 |
29 |
|
30 \solution{ |
|
31 a and b are ok; c is not matched because x4x is not an identifier according to the rules. |
|
32 } |
|
33 |
|
34 |
30 \item Suppose the grammar |
35 \item Suppose the grammar |
31 |
36 |
32 \begin{plstx}[margin=1cm] |
37 \begin{plstx}[margin=1cm] |
33 :\meta{E} ::= \meta{F} \;|\; \meta{F} \cdot \texttt{*} \cdot \meta{F} \;|\; \meta{F} \cdot \backslash \cdot \meta{F}\\ |
38 :\meta{E} ::= \meta{F} \;|\; \meta{F} \cdot \texttt{*} \cdot \meta{F} \;|\; \meta{F} \cdot \backslash \cdot \meta{F}\\ |
34 :\meta{F} ::= \meta{T} \;|\; \meta{T} \cdot \texttt{+} \cdot \meta{T} \;|\; \meta{T} \cdot \texttt{-} \cdot \meta{T}\\ |
39 :\meta{F} ::= \meta{T} \;|\; \meta{T} \cdot \texttt{+} \cdot \meta{T} \;|\; \meta{T} \cdot \texttt{-} \cdot \meta{T}\\ |
41 \meta{F} and \meta{T} are ``exchanged'' in this grammar in comparison with |
46 \meta{F} and \meta{T} are ``exchanged'' in this grammar in comparison with |
42 the usual grammar for arithmetic expressions. What does this mean in terms |
47 the usual grammar for arithmetic expressions. What does this mean in terms |
43 of precedences of the operators? |
48 of precedences of the operators? |
44 |
49 |
45 \solution{ |
50 \solution{ |
|
51 \begin{tikzpicture}[level distance=10mm, black,sibling distance=10mm] |
|
52 \node {\meta{E}} |
|
53 child[sibling distance=20mm] {node {\meta{F}} |
|
54 child {node {\meta{T}} |
|
55 child[sibling distance=5mm] {node {(}} |
|
56 child[sibling distance=5mm] {node {\meta{E}} |
|
57 child {node {\meta{F}} |
|
58 child {node {\meta{T}} child {node {3}}} |
|
59 child {node {+}} |
|
60 child {node {\meta{T}} child {node {3}}} |
|
61 } |
|
62 } |
|
63 child[sibling distance=5mm] {node {)}} |
|
64 } |
|
65 child {node {+}} |
|
66 child {node {\meta{T}} |
|
67 child[sibling distance=5mm] {node {(}} |
|
68 child[sibling distance=5mm] {node {\meta{E}} |
|
69 child {node {\meta{F}} |
|
70 child {node {\meta{T}} child {node {2}}} |
|
71 } |
|
72 child {node {*}} |
|
73 child {node {\meta{F}} |
|
74 child {node {\meta{T}} child {node {3}}} |
|
75 } |
|
76 } |
|
77 child[sibling distance=5mm] {node {)}} |
|
78 } |
|
79 }; |
|
80 \end{tikzpicture} |
|
81 |
|
82 |
46 For the second part "1+2*3" will be parsed as (1+2)*3, meaning + and - bind |
83 For the second part "1+2*3" will be parsed as (1+2)*3, meaning + and - bind |
47 tighter than * and $\backslash$ |
84 tighter than * and $\backslash$ |
48 } |
85 } |
49 |
86 |
50 \item Define what it means for a grammar to be ambiguous. Give an example of |
87 \item Define what it means for a grammar to be ambiguous. Give an example of |
74 |
111 |
75 (i) Give a grammar that can recognise such boolean expressions |
112 (i) Give a grammar that can recognise such boolean expressions |
76 and (ii) give a sample string involving all rules given in 1.-4.~that |
113 and (ii) give a sample string involving all rules given in 1.-4.~that |
77 can be parsed by this grammar. |
114 can be parsed by this grammar. |
78 |
115 |
|
116 \solution{ |
|
117 The simplest grammar is |
|
118 |
|
119 \begin{plstx}[margin=1cm] |
|
120 :\meta{B} ::= true \;|\; false \;|\;\meta{B} \cdot $\wedge$ \cdot \meta{B} \;|\; \meta{B} \cdot $\vee$ \cdot \meta{B} |
|
121 \;|\; $\neg$\meta{B} \;|\; (\cdot\meta{B}\cdot)\\ |
|
122 \end{plstx} |
79 |
123 |
|
124 This is unfortunately a left-recursive grammar. Giving a not left-recursive one is a bit more involved. |
|
125 } |
80 |
126 |
81 \item Parsing combinators consist of atomic parsers, alternative |
127 \item Parsing combinators consist of atomic parsers, alternative |
82 parsers, sequence parsers and semantic actions. What is the purpose |
128 parsers, sequence parsers and semantic actions. What is the purpose |
83 of (1) atomic parsers and of (2) map-parsers (also called semantic actions)? |
129 of (1) atomic parsers and of (2) map-parsers (also called semantic actions)? |
84 |
130 |