Institute Academy

Understanding Parsing using Examples In every example, we introduce a new start symbol (S’), and define a new production from this new start symbol to the original start symbol of the grammar. Consider the following grammar (putting an explicit end-marker $ at the end of the first production): (1) S’ → S$ (2) S → Sa (3) S → b For this example, the NFA for the stack can be shown as follows: After doing ε-closure, the resulting DFA is as follows:   The states of DFA are also called “Canonical Collection of Items”. Using the above notation, the ACTION-GOTO table can be shown as follows: Notice that there are two entries for state 2 on input ‘a’. So, this cannot be LR(0) grammar. So, the next enhancement is to look into the FOLLOW set of S’ (which is {$}) and it is different from the shift symbol, this shift-reduce conflict can be resolved easily by reducing on input if it belongs to the FOLLOW set for S’. This enhancement to parsing is called SLR(

Buttom Up Parsing or Shift-reduce parsing Buttom Up Parsing  is also known as Shift-reduce parsing. Buttom Up Parsing  or shift reducing parsing attempts to construct a parse tree for an input string beginning at the leaves and working up towards the root. In other words, it is a process of “reducing” (opposite of deriving a symbol using a production rule) a string w to the start symbol of a grammar. At every (reduction) step, a particular substring matching the RHS of a production rule is replaced by the symbol on the LHS of the production. A general form of shift-reduce parsing is LR (scanning from Left to right and using Right-most derivation in reverse) parsing, which is used in a number of automatic parser generators like Yacc, Bison, etc. Here are the definitions of some commonly used terminologies in this context. Implementation of Shift-Reduce Parsing A convenient way to implement a shift-reduce parser is to use a stack to hold grammar symbols and an input

Handles A “handle” of a string is a substring that matches the RHS of a production and whose reduction to the non-terminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol. If S →* αAw →* αβw, then A → β in the position following α is a handle of αβw. In such a case, it is suffice to say that the substring β is a handle of αβw, if the position of β and the corresponding production are clear. Consider the following grammar: E → E + E | E * E | (E) | id and a right-most derivation is as follows: E → E + E → E+ E * E → E + E * id3 → E + id2 * id3 → id1 + id2 * id3 The id’s are subscripted for notational convenience. Note that the reduction is in the opposite direction from id1 + id2 * id3 back to E, where the handle at every step is underlined.