.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Susan Rodger and Cliff Shaffer
   :requires: Deterministic Pushdown Automata
   :satisfies: Deterministic Pushdown Automata Grammars
   :topic: Finite Automata

.. slideconf::
   :autoslides: False


Grammars for Deterministic Context-free Languages
=================================================

.. slide:: Deterministic vs. Non-deterministic PDAs and Grammars

   | Now we know that:
   |    All CFL can be generated by a CFG, and implemented
        by a NPDA.
   |    Not all CFL can be generated using a DPDA.
   |    So some CFG are associated with only non-deterministic PDAs.
   |    Nondeterminism gives us something more in terms of capability.


.. slide::  Why do we care?

   | Because we want to parse efficiently.
   | This means, we want to quickly determine if a given string can
     be generated from a given grammar.
   | Determinism seems to be a fundamental requirement if we hope
     to do this.


.. slide:: PDAs and Parsing

   | Think of a PDA as a parsing device.
   |    No backtracking :math:`\Rightarrow` can make a decision at
        every step on what to do next.
   |    This is the same as knowing which grammar production comes next.
   |    Clearly linear time when the grammar has been simplified (no
        unit productions), because every derivation step consumes an
        input character.
   |    Oops... except for :math:`\lambda` productions. But actually,
        these are not really a problem either.


.. slide:: Top-down Parsing with Lookahead

   | Start with the start symbol
   | Scan left-to-right through the string.
   | At each step, we want only to follow one rule when we look at the
     current character.
   | Perhaps we don't see a production for the current character, but
     instead pop something off the stack (:math:`\lambda` production).
   |    (BTW: This is why :math:`\lambda` productions are still
         linear, if we don't put too much on the stack when we process
         a character.)


.. slide:: S-grammars

   | Recall that an S-grammar has all productions of the form:
   |    :math:`A \rightarrow ax`
   | where :math:`A \in V`, :math:`a \in T`, and :math:`x \in V^*` AND any
     pair :math:`(A, a)` can occur in at most one rule.
   | Obviously this can be parsed efficiently.
   | But, s-grammars are more restrictive than we want.
   |    Lots of useful language constructs cannot be defined using an
        s-grammar.
   | We want to generalize as much as we can to capture a broader
     subset of CFLs


.. slide:: LL(k) Grammars

   | LL means "left-to-right" and "left-most derivation" is
     constructed.
   | :math:`k` means that we can look ahead at most :math:`k-1`
     characters.
   | Every s-grammar is LL, but so are more grammars.


.. slide:: LL Example 1

   | Consider this grammar:
   |    :math:`S \rightarrow aSb \mid ab`
   | This is not an s-grammar.
   | But, this **is** an LL grammar.
   | By looking at the next two characters, we always know which rule
     to apply.
   |    If we see :math:`ab`, then apply :math:`S \rightarrow ab`.
   |    Otherwise, apply :math:`S \rightarrow aSb`


.. slide:: LL Example 2 (1)

   | Consider this grammar:
   |    :math:`S \rightarrow SS \mid aSb \mid ab`
   | This is a useful grammar! It captures nested parentheses.
   | This is **not** an LL(k) grammar for any :math:`k`.
   |    << Why not?? >>


.. slide:: LL Example 2 (2)

   | Just because the grammar is not LL(k) does not mean that the
     language might not be deterministic.
   | The reasoning for why this was not LL(k) should help you to see
     how to fix the grammar.
   | Consider this grammar: :math:`S \rightarrow aSbS \mid \lambda`
   |    This is LL.
   | Example: Derive :math:`w = abab`.
   |    :math:`S \Rightarrow aSbS \Rightarrow abS \Rightarrow abaSbS \Rightarrow ababS \Rightarrow abab`.
   |    When the input next input symbol is :math:`a`, we must use
        :math:`S \rightarrow aSbS`.
   |    When the input next input symbol is :math:`b` or string is
        empty, we must use :math:`S \rightarrow \lambda`.


.. slide:: LL Example 2 (3)

   | One last problem: This grammar accepts the empty string.
   | If we don't like that, then there is an easy fix.
   |    Just define a new start symbol that avoids the :math:`\lambda`
        production.
   |       :math:`S_0 \rightarrow aSbS`
   |       :math:`S \rightarrow aSbS \mid \lambda`