answersLogoWhite

0


Best Answer

Bottom-up parsing

This approach is not unlike solving a jigsaw puzzle. We start at the bottom of the parse tree with individual characters. We then use the rules to connect the characters together into larger tokens as we go. At the end of the string, everything should have been combined into a single big S, and S should be the only thing we have left. If not, it's necessary to backtrack and try combining tokens in different ways.

With bottom-up parsing, we typically maintain a stack, which is the list of characters and tokens we've seen so far. At each step, the stack is "reduced" as far as possible by combining characters into larger tokens.

Top-down parsing

For this approach we assume that the string matches S and look at the internal logical implications of this assumption. For example, the fact that the string matchesSlogically implies that either (1) the string matches xyz or (2) the string matchesaBC. If we know that (1) is not true, then (2) must be true. But (2) has its own further logical implications. These must be examined as far as necessary to prove the base assertion.

Example

String is acddf.

Steps

· Assertion 1: acddf matches S

oAssertion 2: acddf matches xyz:

oAssertion is false. Try another.

oAssertion 2: acddf matches aBC i.e. cddf matches BC:

  • Assertion 3: cddf matches cC i.e. ddf matches C:

§ Assertion 4: ddf matches eg:

§ False.

§ Assertion 4: ddf matches df:

§ False.

  • Assertion 3 is false. Try another.
  • Assertion 3: cddf matches cdC i.e. df matches C:

§ Assertion 4: df matches eg:

§ False.

§ Assertion 4: df matches df:

§ Assertion 4 is true.

  • Assertion 3 is true.

oAssertion 2 is true.

· Assertion 1 is true. Success!

Parse trees

S

|

S

/|\

a B C

| |

S

/|\

a B C

| |

c

S

/|\

a B C

/| |

c d

S

/|\

a B C

/| |\

c d d f

User Avatar

Wiki User

11y ago
This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: Difference between top down and bottom up parsing in compiler design?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Continue Learning about Engineering

What is the difference between first floor from ground floor?

Actually, there is not much difference, but a ground floor is usually the very bottom one and the first floor is usually the one above


What is the difference between an S trap and P trap?

A P trap exits horizontal from the back of the toilet and a S trap exits vertical from the bottom of the toilet.


What is the difference between inverted beam and drop beam?

An inverted beam is a beam whose bottom is the same as the slab. A drop beam is a beam that is put under the structural member it supports.


What is the difference between a river's suspended load and its bed load?

The difference between a suspended load and a bead load is a suspended load consists of the small particles or rock materials that are dispersed throughout the water and easily carried downstream. The bead load consists of the larger particles that are dragged and bounced along near the bottom of the river.


What and the difference between a rivers suspended load and it and bed load?

The difference between a suspended load and a bead load is a suspended load consists of the small particles or rock materials that are dispersed throughout the water and easily carried downstream. The bead load consists of the larger particles that are dragged and bounced along near the bottom of the river.

Related questions

Why stack is preferable data structure for bottom up parsing?

Stacks are not only the preferred data structure for bottom up parsing, they are the only data structure suitable for bottom up parsing. Bottom-up parsing is usually referred to as depth-first search. Top-down parsing is referred to as breadth-first search. The two are exactly the same in terms of implementation, the difference is only in the structure used to store information collated from the previous iterations. With top-down parsing you use a queue, pushing to the back and popping from the front. With bottom-up parsing you use a stack, pushing to and popping from the back.


Difference between top down and bottom up parsing?

Bottom-up parsing (also known as shift-reduce parsing) is a strategy for analyzing unknown data relationships that attempts to identify the most fundamental units first, and then to infer higher-order structures from them. It attempts to build trees upward toward the start symbol. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis.


What is the role of a parser in compiler design?

· In the compiler model, the parser obtains a string of tokens from the lexical analyser, and verifies that the string can be generated by the grammar for the source language.· The parser returns any syntax error for the source language.· There are three general types' parsers for grammars.· Universal parsing methods such as the Cocke-Younger-Kasami algorithm andEarley's algorithm can parse any grammar. These methods are too inefficient to use in production compilers.· The methods commonly used in compilers are classified as either top-down parsing or bottom-up parsing.· Top-down parsers build parse trees from the top (root) to the bottom (leaves).· Bottom-up parsers build parse trees from the leaves and work up to the root.· In both case input to the parser is scanned from left to right, one symbol at a time.· The output of the parser is some representation of the parse tree for the stream of tokens.· There are number of tasks that might be conducted during parsing. Such as;o Collecting information about various tokens into the symbol table.o Performing type checking and other kinds of semantic analysis.o Generating intermediate code.


What is the role of parser in compiler design?

· In the compiler model, the parser obtains a string of tokens from the lexical analyser, and verifies that the string can be generated by the grammar for the source language.· The parser returns any syntax error for the source language.· There are three general types' parsers for grammars.· Universal parsing methods such as the Cocke-Younger-Kasami algorithm andEarley's algorithm can parse any grammar. These methods are too inefficient to use in production compilers.· The methods commonly used in compilers are classified as either top-down parsing or bottom-up parsing.· Top-down parsers build parse trees from the top (root) to the bottom (leaves).· Bottom-up parsers build parse trees from the leaves and work up to the root.· In both case input to the parser is scanned from left to right, one symbol at a time.· The output of the parser is some representation of the parse tree for the stream of tokens.· There are number of tasks that might be conducted during parsing. Such as;o Collecting information about various tokens into the symbol table.o Performing type checking and other kinds of semantic analysis.o Generating intermediate code.


What is the latest trends in compiler constraction?

bottom up methods


What is the difference between top and bottom in lesbian relationships?

the top is the giver while the bottom is the receiver


What is the difference between the core and the lithosphere?

The difference between the core and the lithosphere is the core is on the top of the lithosphere and the lithosphere is on the bottom of the core


What is the difference between a square pyramid and a pyramid?

the difference between them is that the bottom face is different one of them is a rectangle and one of them is a square


What is one difference between sandy-bottom and live-bottom habitats?

The sandy-bottom is all sand, and the live-bottom is plant life.


What is the difference between a square pyramid and a rectangular pyramid?

the difference between them is that the bottom face is different one of them is a rectangle and one of them is a square


What is the difference between a surfboard and a ski?

Surfboard has a sharp keel on its bottom while the ski bottom is smooth.


What is the difference between a rectangular pyramid and a square pyramid?

One has a rectangle on the bottom and the other has a square on the bottom.