80 \begin{center} |
80 \begin{center} |
81 \tt Time flies like an arrow. Fruit flies like bananas. |
81 \tt Time flies like an arrow. Fruit flies like bananas. |
82 \end{center} |
82 \end{center} |
83 |
83 |
84 \noindent |
84 \noindent |
85 from natural languages were the meaning of \emph{flies} depends on the |
85 from natural languages where the meaning of \emph{flies} depends on the |
86 surrounding \emph{context} are avoided as much as possible. Here is |
86 surrounding \emph{context} are avoided as much as possible. Here is |
87 an interesting video about C++ not being a context-free language |
87 an interesting video about C++ not being a context-free language |
88 |
88 |
89 \begin{center} |
89 \begin{center} |
90 \url{https://www.youtube.com/watch?v=OzK8pUu4UfM} |
90 \url{https://www.youtube.com/watch?v=OzK8pUu4UfM} |
366 : \meta{B} ::= 0 \cdot \meta{B} | 1 \cdot \meta{B} | 0 | 1\\ |
366 : \meta{B} ::= 0 \cdot \meta{B} | 1 \cdot \meta{B} | 0 | 1\\ |
367 \end{plstx} |
367 \end{plstx} |
368 |
368 |
369 \noindent |
369 \noindent |
370 The point is that we can in principle transform every left-recursive |
370 The point is that we can in principle transform every left-recursive |
371 grammar into one that is non-left-recursive one. This explains why often |
371 grammar into one that is non-left-recursive. This explains why often |
372 the following grammar is used for arithmetic expressions: |
372 the following grammar is used for arithmetic expressions: |
373 |
373 |
374 \begin{plstx}[margin=1cm] |
374 \begin{plstx}[margin=1cm] |
375 : \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\ |
375 : \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\ |
376 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\ |
376 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\ |
378 \end{plstx} |
378 \end{plstx} |
379 |
379 |
380 \noindent |
380 \noindent |
381 In this grammar all $\meta{E}$xpressions, $\meta{T}$erms and |
381 In this grammar all $\meta{E}$xpressions, $\meta{T}$erms and |
382 $\meta{F}$actors are in some way protected from being |
382 $\meta{F}$actors are in some way protected from being |
383 left-recusive. For example if you start $\meta{E}$ you can derive |
383 left-recursive. For example if you start $\meta{E}$ you can derive |
384 another one by going through $\meta{T}$, then $\meta{F}$, but then |
384 another one by going through $\meta{T}$, then $\meta{F}$, but then |
385 $\meta{E}$ is protected by the open-parenthesis in the last rule. |
385 $\meta{E}$ is protected by the open-parenthesis in the last rule. |
386 |
386 |
387 \subsection*{Removing $\epsilon$-Rules and CYK-Algorithm} |
387 \subsection*{Removing $\epsilon$-Rules and CYK-Algorithm} |
388 |
388 |
406 |
406 |
407 It turns out we can also by some generic transformations eliminate |
407 It turns out we can also by some generic transformations eliminate |
408 $\epsilon$-rules from grammars. Consider again the grammar above for |
408 $\epsilon$-rules from grammars. Consider again the grammar above for |
409 binary numbers where have a rule $\meta{B'} ::= \epsilon$. In this case |
409 binary numbers where have a rule $\meta{B'} ::= \epsilon$. In this case |
410 we look for rules of the (generic) form \mbox{$\meta{A} := |
410 we look for rules of the (generic) form \mbox{$\meta{A} := |
411 \alpha\cdot\meta{B'}\cdot\beta$}. That is there are rules that use |
411 \alpha\cdot\meta{B'}\cdot\beta$}. That is, there are rules that use |
412 $\meta{B'}$ and something ($\alpha$) is in front of $\meta{B'}$ and |
412 $\meta{B'}$ and something ($\alpha$) is in front of $\meta{B'}$ and |
413 something follows ($\beta$). Such rules need to be replaced by |
413 something follows ($\beta$). Such rules need to be replaced by |
414 additional rules of the form \mbox{$\meta{A} := \alpha\cdot\beta$}. |
414 additional rules of the form \mbox{$\meta{A} := \alpha\cdot\beta$}. |
415 In our running example there are the two rules for $\meta{B}$ which |
415 In our running example there are the two rules for $\meta{B}$ which |
416 fall into this category |
416 fall into this category |
417 |
417 |
418 \begin{plstx}[margin=1cm] |
418 \begin{plstx}[margin=1cm] |
419 : \meta{B} ::= 0 \cdot \meta{B'} | 1 \cdot \meta{B'}\\ |
419 : \meta{B} ::= 0 \cdot \meta{B'} | 1 \cdot \meta{B'}\\ |
420 \end{plstx} |
420 \end{plstx} |
421 |
421 |
422 \noindent To follow the general scheme of the transfromation, |
422 \noindent To follow the general scheme of the transformation, |
423 the $\alpha$ is either is either $0$ or $1$, and the $\beta$ happens |
423 the $\alpha$ is either is either $0$ or $1$, and the $\beta$ happens |
424 to be empty. So we need to generate new rules for the form |
424 to be empty. So we need to generate new rules for the form |
425 \mbox{$\meta{A} := \alpha\cdot\beta$}, which in our particular |
425 \mbox{$\meta{A} := \alpha\cdot\beta$}, which in our particular |
426 example means we obtain |
426 example means we obtain |
427 |
427 |