What do you understand by L-attributed definition? Give example. Describe with diagram the working process of Lexical Analyzer. Describe LR parsing with block diagram.

L-attributes: All variables have an attribute associated with it, getting some values.

A→BCD.

A.s=f(B.s, C.s, D.s).

A is getting values from its children. Such an attribute is called Synthesized attribute because they are synthesizing the value of the attribute from the children.

A→BCD, if say C is getting the values from its parent A or its left siblings B,  it is called inherited attribute. C.i=A.i; C.i=B.i.

An L-attributed SDT (Syntax Directed Translation)

Uses both inherited and synthesized attributes.

Semantic actions are placed anywhere on RHS. A→{}BC | D{}E | FG{}

Attributes are evaluated by traversing parse tree by depth first search, left to right.  

Ex: A→BC {B.s=A.s}

We can see that is inherited attribute. So, it is L-attributed. 

Lexical analysis reads characters from left to right and groups into tokens. A simple way to build lexical analyzer is to construct a diagram to illustrate the structure of tokens of the source program. We can also produce a lexical analyzer automatically by specifying the lexeme patterns to a lexical-analyzer generator and compiling those patterns into code that functions as a lexical analyzer. This approach makes it easier to modify a lexical analyzer, since we have only to rewrite the affected patterns, not the entire program. Three general approaches for implementing lexical analyzer are:

• Use lexical analyzer generator (LEX) from a regular expression based specification that provides routines for reading and buffering the input.
• Write lexical analyzer in conventional language using I/O facilities to read input.
• Write lexical analyzer in assembly language and explicitly manage the reading of input.

The speed of lexical analysis is a concern in compiler design, since only this phase reads the source program character-by character.

Since the lexical analyzer is the part of the compiler that reads the source text, it may perform certain other tasks besides identification of lexemes.

• One such task is stripping out comments and whitespace (blank, newline, tab, and perhaps other characters that are used to separate tokens in the input).
• Another task is correlating error messages generated by the compiler with the source program. For instance, the lexical analyzer may keep track of the number of newline characters seen, so it can associate a line number with each error message. In some compilers, the lexical analyzer makes a copy of the source program with the error messages inserted at the appropriate positions.
• If the source program uses a macro-preprocessor, the expansion of macros may also be performed by the lexical analyzer. It is the first phase of a compiler. It reads source code as input and sequence of tokens as output. This will be used as input by the parser in syntax analysis. Upon receiving ‘getNextToken’ from parser, lexical analyzer searches for the next token.
• Some additional tasks are: eliminating comments, blanks, and tab and newline characters, providing line numbers associated with error messages and making a copy of the source program with error messages.

Some of the issues are: simpler design, compiler efficiency is improved and compiler portability is enhanced. 

Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches the root node. Here, we start from a sentence and then apply production rules in reverse manner in order to reach the start symbol. The image given below depicts the bottom-up parsers available. 

Shift-Reduce Parsing

Shift-reduce parsing use two unique steps for bottom-up parsing. These steps are known as shift-step and reduce-step.

• Shift step: The shift step refers to the advancement of the input pointer to the next input symbol, which is called the shifted symbol. This symbol is pushed onto the stack. The shifted symbol is treated as a single node of the parse tree.
• Reduce step: When the parser finds a complete grammar rule (RHS) and replaces it to (LHS), it is known as reduce-step. This occurs when the top of the stack contains a handle. To reduce, a POP function is performed on the stack which pops off the handle and replaces it with LHS non-terminal symbol.

LR Parser

The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar which makes it the most efficient syntax analysis technique. LR parsers are also known as LR(k) parsers, where L stands for left-to-right scanning of the input stream; R stands for the construction of right-most derivation in reverse, and k denotes the number of lookahead symbols to make decisions. In LR(0), we write the reduce steps for all the terminals throughout the row.

There are three widely used algorithms available for constructing an LR parser:

• SLR(1) – Simple LR Parser:
  • Works on smallest class of grammar
  • Few number of states, hence very small table
  • Simple and fast construction
  • In SLR(1), we write the reduce steps for only the follow sets of the left-hand side.
• CLR(1) – Canonical LR Parser:
  • Works on complete set of LR(1) Grammar
  • Generates large table and large number of states
  • Slow construction
  • It is actually constructed by LR(0) items + lookaheads.
  • In CLR(1), we write the reduce steps for only the lookaheads.
• LALR(1) – Look-Ahead LR Parser:
  • Works on intermediate size of grammar
  • Number of states are same as in SLR(1)
  • It is actually reduced CLR(1).

LR Parsing Algorithm

Here we describe a skeleton algorithm of an LR parser:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

1. Does a rightmost derivation in reverse.
2. Ends with the root nonterminal on the stack.
3. Starts with an empty stack.
4. Uses the stack for designating what is already seen.
5. Builds the parse tree bottom-up.
6. Tries to recognize a right hand side on the stack, pops it, and pushes the corresponding nonterminal.
7. Reduces the non-terminals.
8. Reads the terminals while it pushes them on the stack.
9. Post-order traversal of the parse tree.