--- a/hws/hw06.tex Sat Nov 11 10:08:33 2023 +0000
+++ b/hws/hw06.tex Fri Nov 17 20:06:43 2023 +0000
@@ -27,6 +27,11 @@
Observe the maximal munch rule and priorities of your regular
expressions that make the process of lexing unambiguous.)
+\solution{
+ a and b are ok; c is not matched because x4x is not an identifier according to the rules.
+}
+
+
\item Suppose the grammar
\begin{plstx}[margin=1cm]
@@ -43,6 +48,38 @@
of precedences of the operators?
\solution{
+ \begin{tikzpicture}[level distance=10mm, black,sibling distance=10mm]
+ \node {\meta{E}}
+ child[sibling distance=20mm] {node {\meta{F}}
+ child {node {\meta{T}}
+ child[sibling distance=5mm] {node {(}}
+ child[sibling distance=5mm] {node {\meta{E}}
+ child {node {\meta{F}}
+ child {node {\meta{T}} child {node {3}}}
+ child {node {+}}
+ child {node {\meta{T}} child {node {3}}}
+ }
+ }
+ child[sibling distance=5mm] {node {)}}
+ }
+ child {node {+}}
+ child {node {\meta{T}}
+ child[sibling distance=5mm] {node {(}}
+ child[sibling distance=5mm] {node {\meta{E}}
+ child {node {\meta{F}}
+ child {node {\meta{T}} child {node {2}}}
+ }
+ child {node {*}}
+ child {node {\meta{F}}
+ child {node {\meta{T}} child {node {3}}}
+ }
+ }
+ child[sibling distance=5mm] {node {)}}
+ }
+ };
+\end{tikzpicture}
+
+
For the second part "1+2*3" will be parsed as (1+2)*3, meaning + and - bind
tighter than * and $\backslash$
}
@@ -76,7 +113,16 @@
and (ii) give a sample string involving all rules given in 1.-4.~that
can be parsed by this grammar.
+\solution{
+The simplest grammar is
+
+\begin{plstx}[margin=1cm]
+ :\meta{B} ::= true \;|\; false \;|\;\meta{B} \cdot $\wedge$ \cdot \meta{B} \;|\; \meta{B} \cdot $\vee$ \cdot \meta{B}
+ \;|\; $\neg$\meta{B} \;|\; (\cdot\meta{B}\cdot)\\
+\end{plstx}
+This is unfortunately a left-recursive grammar. Giving a not left-recursive one is a bit more involved.
+ }
\item Parsing combinators consist of atomic parsers, alternative
parsers, sequence parsers and semantic actions. What is the purpose