Scribd
Upload
60 views

Group 4&5 Activity Syntax Analyzer

This document discusses top-down and bottom-up parsing. It provides examples of context-free grammars and parses input strings based on these grammars using top-down and bottom-up parsing techniques. For top-down parsing, it discusses leftmost derivations and uses a grammar to construct a parse tree for the token stream "( int )". For bottom-up parsing, it demonstrates shift-reduce parsing using a grammar, explaining shift and reduce actions. It also discusses operator precedence parsing and provides an example of building a parse stack and tree.

Uploaded by

Juan Pransisko
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
60 views

Group 4&5 Activity Syntax Analyzer

This document discusses top-down and bottom-up parsing. It provides examples of context-free grammars and parses input strings based on these grammars using top-down and bottom-up parsing techniques. For top-down parsing, it discusses leftmost derivations and uses a grammar to construct a parse tree for the token stream "( int )". For bottom-up parsing, it demonstrates shift-reduce parsing using a grammar, explaining shift and reduce actions. It also discusses operator precedence parsing and provides an example of building a parse stack and tree.

Uploaded by

Juan Pransisko
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Top-down parsing:

Bottom-up parsing:

COSC 4063 COMPILER DESIGN


EXERCISE ON SYNTAX ANALYSIS

Name: Section: Date:

TOP-DOWN PARSING
I. The role of the parser and Context Free Grammar
TRUE or FALSE
___________ 1. Semantic error are type mismatches between operators and operands.
___________ 2. Any language that can be generated using regular expressions can be generated by a
context-free grammar.
___________ 3. Logical errors can be anything from incorrect reasoning on the part ot the programmer to
use in a program.
___________ 4. Any languages that can be generated by a context-free grammar can also be generated
by any regular expression.
___________ 5. Parse trees have leaves labeled with non-terminals; interior nodes labeled with
terminals.
___________ 6. Cocke-Younger-Kasami and Earleys algorithm are under bottom-up parsing.
___________ 7. A language that can be generated by a grammar is said to be a context-free language. If
two grammars generate the same language, the grammars are said to be equivalent.
___________ 8. E->TE, E->+TE|e, T->FT, T-> *FT|e, F-> ( E )|id. It is an example of bottom-up
parsing.
___________ 9. A derivation is a sequence of sentential forms starting from start symbol.
___________ 10. There are three general types parser for grammars

II. Writing a Grammar


1. In a leftmost derivation, we choose to always reduce the _______________.
2. If a grammar has more than one leftmost derivation for some string, the grammar is
_____________.
3. ____________ is a bad thing if were interested in the structure of the parse tree.
4. Every ____________ corresponds to a unique left-most derivation.
5. In any step of a ___________, there might be several variables that can be reduced by rules of
the grammar.

III. Recursive-Descent Parsing


Construct a parse tree given the following grammar:
E -> T|T+E
T -> int | int * T | ( E )
Token stream is: ( int )
IV. Predictive Parsers
Give the LL (1) Grammar, parse by predictive parsing if the input int*int is accepted and draw its parse
tree.

BOTTOM-UP PARSING

I. Identification
1. It is the reverse of derivation. Thus, aiming to reach the start symbol from the yield of
the grammar.
2. A bottom-up parser traces a in reverse.
3. The general method of bottom-up parsing.
4. Four primary operations/actions of the bottom-up parser.
5. Continuation of 5
6. Continuation of 6
7. Continuation of 7
8. Once the token string is divided, the left substring could be implemented by means of
a
9. It is a form of reduction that allows further reductions back to the start symbol.
10. This is the prefix part of a handle

II. Shift-reduce Parsing


Using the grammar below, parse the string int * int + int
E T | T + E
T int | int * T

Stack Input Action


III. Explanation
1. What is shift-reduce conflict?

2. What is reduce-reduce conflict?

IV. Operator Precedence Parsing


Create a stack and Parse Tree from the following.
id1 + id2 * id3
$ < id1 > + < id2 > * < id3 > $
ANSWERS (Top-down parsing):
I. 1. False 6. False
2. True 7. True
3. True 8. False
4. False 9. True
5. False 10. True

II. 1. Leftmost variable


2. Ambiguous
3. Ambiguity
4. Parse tree
5. Derivation

III.

( E )

int
IV.
Tracing:
BOTTOM-UP PARSING
I. Identification
1. Reduction 6. Accept
2. Rightmost derivation 7. Error
3. Shift-reduce parsing 8. Stack
4. Shift 9. Handle
5. Reduce 10. Viable prefix

II. Shift-Reduce parsing


STACK INPUT ACTION
$ int * int + int Shift
$int * int + int Shift
$int * Int + int Shift
$int * int + int Reduce T int
$int * T + int Reduce T int * T
$T + int Shift
$T + Int Shift
$T + int Reduce T int
$T + T Reduce E T
$T + E Reduce E T + E
$E

III. Explain
1. It is caused when the grammar allows a rule to be reduced for particular token, but, at the
same time, allowing another rule to be shifted for that same token.
2. A reduce/reduce conflict occurs if there are two or more rules that apply to the same
sequence of input

IV. Operator precedence

stack input action


$ id+id*id$ $ <. id shift
$id +id*id$ Id .> + reduceE ->id
$ +id*id$ shift
$+ id*id$ shift
$+id *id$ id .> * reduceE -> id
$+ *id$ shift
$+* id$ shift
$+*id $id .>$ reduceE -> id
$+* $* .>$ reduceE -> E*E
$+ $+ .>$ reduceE -> E+E
$ $ accept
Stack:

Parse tree:

You might also like