Field Reports tell how instructors have used AVs in their teaching.

Interactively learning SLR Parsing and how it fits in with automata theory

No replies
rodger's picture
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-06-05
Points: 196
Susan Rodger
Duke University
CompSci 140: Mathematical Foundations
Term / Date: 
Spring 2009
AVs used: 

This lesson shows how deterministic finite automata (DFA), pushdown automata (PDA) and context-free grammars (CFG) are used in SLR parsing. A previous lesson introduces the idea of top-down and bottom-up parsing, and how to compute FIRST and FOLLOW sets. In this lesson, we first learn how to convert a context-free grammar into a PDA that models the parsing process and then we use JFLAP to enter a grammer and convert that particular grammar into a PDA. The PDA is nondeterministic which can be seen by running input strings. Next we learn how to use an SLR parse table in JFLAP to parse the string, a deterministic process as it uses a look ahead to decide which rule to apply next. Then we learn how to build this SLR parse table by first constructing a special DFA, in which each state has additional information. We then use JFLAP to start with a grammar, build this special DFA and then using the DFA build the LR parse table. Last we talk about how not every CFG can be converted into a LR parse table, there may be conflicts and how to resolve them. We then work a more complicated example of starting with a CFG and creating the SLR parse table, and parsing input with the table. The first example with JFLAP is built by the instructor in front of the class with input from the students. In the second example, the students build the SLR parse table on paper and then one of them describes it and the professor builds it for the class. This lesson is a two-day lesson.