Bottom-Up Parsing

Bottom-Up Parsing

• Parsing begins at the leaves of the parse tree and proceeds towards the root
• It is capable of handling a large class of grammars

Shift-Reduce Parsing

• Aims to construct a parse tree for an input string by starting at the leaves and moving up to the root
• Reduces a string to the grammar's start symbol
• At each reduction step, a substring matching the right side of a production is replaced by the symbol on the left side of that production
• An example grammar is S -> aABe, A -> Abc | b, B -> d
• An example input abbcde can be parsed bottom-up

Handle

• Is a substring that matches the right side of a production

Stack Implementation of Shift-Reduce Parsing

• Employs a stack for grammar symbols and an input buffer for the string to be parsed
• '$' marks the bottom of the stack and the end of the input string
• There are four possible actions: Shift, Reduce, Accept, and Error

Shift

• The next input symbol gets shifted onto the top of the stack

Reduce

• The handle is replaced with a nonterminal symbol

Accept

• The parser declares successful completion of parsing

Error

• The parser identifies a syntax error and invokes an error recovery routine

Conflicts During Shift-Reduce Parsing

• Shift-reduce parsing is not suitable for all context-free grammars
• Ambiguous grammars lead to parsing conflicts
• Resolution involves rewriting the grammar or making appropriate action choices during parsing
• Two types of conflicts: Shift/Reduce and Reduce/Reduce

Shift/Reduce Conflicts

• Must decide whether to shift or reduce, as shown in previous example

Reduce/Reduce Conflicts

• Must decide which production to reduce with
• Example productions include: stmt -> id(param), param -> id, expr -> id(expr) | id

LR Parsers

• An efficient bottom-up syntax analysis technique suitable for a large class of context-free grammars
• "L" stands for left-to-right scanning of input
• "R" stands for constructing a rightmost derivation in reverse
• "k" represents the number of input symbols of lookahead (if omitted, k is assumed to be 1)
• LR parsing is attractive because LR parsers can recognize virtually all programming language constructs for which context-free grammars can be written
• The LR parsing method is a general nonbacktracking shift-reduce parsing method
• The class of grammars parsable by LR methods is a proper superset of those parsable by predictive parsers
• Consists of an Input, an Output, a Stack, a Driver program, and a Parsing table that has two parts (action and goto)

Types of LR Parsers

• Simple LR parser (SLR) is the easiest to implement but least powerful
• Canonical LR parser is the most powerful and most expensive
• Lookahead LR parser (LALR) is intermediate in power and cost
• The LALR method works on programming-language grammars and can be implemented efficiently

LR Parsing Algorithm

• The LR program is the same for all LR parsers
• Only the parsing table changes from one parser to another

Implementation of SLR parser

• The SLR-parser is extremely tedious to build by hand, so needs a generator
• Here are the stages used to build a system for implementing the SLR-parser

Input Stage

• The grammar is read, and grammar symbols (terminals and nonterminals) are specified
• Each grammar production must be on one straight line
• The productions are numbered

Compute First & Follow Stage

• First & Follow are detected for each nonterminal

Construct DFA Stage

• Using a deterministic finite automaton (DFA), the SLR-parser determines when to shift and reduce
• DFA edges are labeled by grammar symbols (terminals & nonterminals)
• The input begins with S'(root), indicating that it begins with any possible right-hand side of an S-production

State0/State1

• A production combined with the dot(.) shows a position of the parser
• For each production, there are three cases to examine for the symbol after the dot:

Symbol is Null

• If dot has occurred at the end of the right side of a production, there is no new state

Symbol is '$' Sign

• If the symbol is the '$' sign, then there is no new state

Symbol is a Terminal or Nonterminal

• Start a new state with current production after the dot has been proceeded one step forward
• If the symbol that has been occurred after the dot(in new position) is nonterminal such as A, add all possible right hand side of A to a new state
• Any newly built state must be stored in a buffer and compared with previous states in DFA
• If there is no similarity, the new state is added to DFA and given a new number

Construct SLR Table Stage

• The SLR-table is a data structure of rows equal to the number of states in DFA, plus columns equal to grammar symbols and the "$" sign symbol
• Data structures provide fast treatment and retrieving of information
• Two subtables are created

Action Table

• Consists of rows equal to the number of states in DFA, and columns equal to the terminals plus "$" symbol

Goto Table

• Consists of the same number of rows as the action table, and columns equivalent to nonterminals

Kinds of Actions

• The elements in the SLR-table are labeled with four kinds of actions:
• Sn: Shift into state n
• gn: goto state n
• rk: reduce by production k
• a: accept
• error (denoted by blank entry in the table) To construct this table, the actions on the table's cells must pass to each state in DFA individually

Shift Action and Goto Action

• The shift & goto action can be labeled according the edge which has been moved from the current state(n) to the new state
• If the edge was terminal symbol (t), the Cell[n-1,t]= sn
• If the edge was nonterminal symbol (N), the Cell[n-1,N]= gn
• If there are production in current state has the form A -> β. (the dot in the end of right hand side, β is any string ), then the action is reduce
• Reduce means Cell[n-1,f]=rk { f in Follow(A), k is the no. of production}
• If there are production in current state has the form A -> β.$ {the dot occurred before $ sign, β is any string },then the action is accept
• Accept means Cell[n-1,$]=a
• Final step indicates, any free cell in row n-1 means an error action
• Repeat the steps for each state in DFA

Implement LR Algorithm

• Suppose the input string is "x+x"
• After inserting the input string, the LR-program is executed

Semantic Analysis

• This compiler phase connects variable definitions to their uses and checks for correct expression types
• Static type checking distinguishes this from dynamic type checking during target program execution
• This phase maintains symbol tables and their identifiers' types and locations

Type Checks

• Report an error if an operator is applied to an incompatible operand

Flow of Control Checks

• Ensure statements causing control flow to transfer have a destination
• A "break" statement in 'C' must have an enclosing while, for, or switch statement or else an error arises

Uniqueness Checks

• Objects must be defined exactly once
• 'Pascal' requires unique declaration of identifiers

Name-Related Checks

• Ensure that a name is the same in multiple cases
• 'Ada', a loop or block name must match at the beginning and end

Type System

• Based on language's syntactic constructs, notation of types, and rules for assigning types
• When both operands of arithmetic operators "addition", "subtraction", and "multiplication" are of type integer then the result is of type integer
• When the type of operand is T, the type of result is ' pointer to T '

Classifying Types

• Classify type into 3 categories
  • Basic types include atomic types with no internal structure like: Boolean, Integer, Real, Char, Subrange, Enumerated, and special types such as "type-error, void "
• Construct, constructs types from basic or complex types: array, struct, set
• Complex types like: link list, tree, pointer
• The Type system is a collection of rules for assigning type expressions to the various parts of a program
• The type checker implements a type system

Specification of a Simple Type Checker

• The type checker follows a translation scheme synthesizing an expression's type from its subexpressions
• Each identifier's type has to be declared before its use
• The grammar represents a represented by P (nonterminal), a queue of declarations D as well as a single expression E
• Type checker (translation scheme) produce parts that save identifier types

Type Checking

• Semantic rules include
  • literal is character
  • num is an integer
• Lookup( e ) to fetch saved types in ST (symbol table), when identifier "e" appears in an expression
• Applies (mod) to two subexpressions
  • E.type is an integer when E1.type and E2.type are integers, throw an error if not
• An array reference checks the following
• E.type is t when E.type is an array with parameters and the other type is an integer, throw an error if not

Statements

• the following is true
  • S.type is void if the types are equal, else error
  • S.type is boolean if the types are valid, or an error
  • S.type is void if all S types are valid or void, else error

Intermediate Code Generation (IR)

• IR is an internal form of a program created by the compiler while translating the program from a H.L.L to L.L.L.(assembly or machine code).
• The backend of compiler uses IR to generate target code
• A machine independent IR offers the following benefits
  • Compiler for machine created by combining backend for the new machine into the existing backend
  • Optimization strategy better performed on IR than language program
• IR becomes a more attractive form of target code

Tow Kinds of Intermediate Representations

• Syntax tree, postfix notation
• DAG carries same data as tree, expressed in a compact way (common subexpression identified)
• Postfix notation linearizes the syntax tree
• The representations above are as follows
• The expression and representations

Three Address code

• The code is carried out as a statement
• The arithmetic functions utilize X-Y op Z
• The components in the code are compiler generated temporary

Three Address code Statements

• There are assignment, arthimetic and logic operators in a binary format
  • Unary operators are expressed also
• Copy statement are present
• Unconditional, conditional jumps included with param call and code
• The code is called recursively
• The memory, data are managed

How the Code gets Implemented

• The quadruples, the triples, are coded in a four field record, these values help the code work fast

Code Optimization

• Compilers produce code as good as from the human hand
• Accomplishes goals with a proper function with a compiler that improves code functions as well
• Code optimization structures syntax, simplifies and takes advantage of specific machines, its aim is to
  • Run faster
• Utilize less space
• Improve space and run time
• Optimizer should not alter an output
• Transformations must accelerate processing
• Optimizations happen at various positions in the machine
  • High level
• Middle level
• Low level
• Optimizer implementations are the following
  • Implement high level explicit operations in memory
• Middlecode operates independently with all targets

Basic Blocks

• The code is in sequence, has instructions

Block setting the following

• Instruction set start
• Code is first
• Jumps operate on targets and include everything
  • There's a block beginning
• Repeats until the end with instructions

Data Flow Analysis Algorithm

• Needs compiler optimization and to collect data from across the language
• In order to optimize a compiler, information about a program as a whole needs to be collected and distributed to each block in the flow graph, DFA provides information about how program execution will manipulate data.
• DFAs help data and information gathering
  • Definations are used and so forth

The Analysis

• Definations lead to what follows

• A block that is not defined in B

• Assignments are in B then it contains all assignments

  • The set of defs hitting start

• The definations reach the end

  • The algorithm for calculation

• Examples

  • Shows the defs in blocks

Loop Information

• Iteration causes repetition that becomes prime point of optimization
  • This determines codes in languages
• Blocks, headers, are the prime factors

Code optimization methods

• The transformation occurs locally when the statements are considered

Local Transformation

• Code is deleted
• Expressions in code is restructured
  • Equations are expressed cheaply

Global transformations

• The data is expressed cheaply
• The code is deleted
• Data is expressed as code and is removed from the program, what code can get reused
• The loop is the key optimization step and decreases in memory and processing. Code gets reused and is reused with all steps