Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Automata & Computation Expert

You have to design a syntactic analyzer for the language specified by the grammar below. We are using the following convention: Terminals (lexical elements) are represented with the bold courier font like this. Non-terminals are represented in angle brackets . The character ε (epsilon) represents an empty stream. The non-terminal is the starting symbol of the grammar.

Grammar

::= *
::= class id {**};
::= program;*
::= id()
::= ;
::= {**}
::= id*;
::= ;
| if()thenelse;
| while()do;
| read();
| write();
| return();
::= {*} | | ε
::= |
::= |
::= + | -
::= |
::=
| *id()
| num
| ()
| not
|
::= *id*
::= id*.
::= []
::= [ int ]
::= integer | real | id
::= id** | ε
::= * | ε
::= ,id*
::= ,

Operators and additional lexical conventions

::= =
::= == | <> | < | > | <= | >=
::= + | - | or
::= * | / | and

id ::= follows specification for identifiers found in assignment#1
num ::= follows specification for numbers found in assignment#1
int ::= *
::= 1..9
::= | 0

For example, the non-terminal is a generalization of the addition operators tokens +, - and or. The use of this notation here does not necessarily imply that you have to define a new type of token in your lexical analyzer. Also, id and num are tokens that refer to the lexical conventions given in the first assignment. Note that a new lexical convention for the token int has been added.

Work to be done

• Analyze the syntactical definition given on the first page (and the additional lexical definition for the token int). Remove all the * notations and replace them by list-generating productions. List in your documentation all the ambiguities and left recursions, or any error you may find in the grammar. Modify the productions so that the left recursions and ambiguities are removed without modifying the language. You should obtain a set of productions that can be parsed using the top-down predictive parsing method. Include the transformed grammar in your documentation.

• Derive the FIRST and FOLLOW sets for each non-terminal in your transformed grammar and list them in your documentation.

• Implement a predictive parser (recursive descent or table-driven) for your modified set of grammar rules.

• Your parser should optionally output to a file the derivation that derives the source program from the starting symbol.

• The parser should call your lexical analyzer as developed in assignment 1 when it needs a new token.

• The parser should properly identify the errors in the input program and print a meaningful message to the user for each error encountered. The parser should implement an error recover method that permits to report all errors. The error messages should be informative on the nature of the errors, as well as the location of the errors in the input file.

• In this assignment, you only check the syntactic correctness of the program, i.e., check whether the source program can be parsed according to the grammar. Do not check the semantic correctness of the program in this assignment.

• Write a set of source files that enable to test the parser for all syntactical structures involved in the language. Include cases testing for a variety of different errors to demonstrate the accuracy of your error reporting and recovery.

Automata & Computation, Computer Science

  • Category:- Automata & Computation
  • Reference No.:- M9132039

Have any Question?


Related Questions in Automata & Computation

Models of computation assignment -purpose - to improve and

Models of Computation Assignment - Purpose - To improve and consolidate your understanding of regular and context-free languages, finite-state and pushdown automata. To develop skills in analysis and formal reasoning abo ...

Regular expressions automatacomputabilitytheory of

Regular expressions, automata/computability/theory of computation How would I go about interpreting regular expressions? For example, how would I interpret the following in English: (0+1)*011 0*1*2* 0^(+)1^(+)2^(+)

Iot and data analytics1 analyse the taskanalyse what is

IOT and data analytics 1. Analyse the Task Analyse what is expected of you. This includes careful reading of the assignment task as specified in the Subject Outline. The executive summary of the research project is to be ...

Question 1hoare logic semantics for each of the parts below

Question 1 Hoare Logic Semantics For each of the parts below, justify your answer briefly. 1. For which programs S does {False} S {True} hold? 2. For which programs S does {True} S {False} hold? 3. For which programs S d ...

Prove or disprove the following proposed inference rules

Prove or disprove the following proposed inference rules for functional dependencies. A proof should be made by using the reflexive, augmentation, transitive, decomposition, union, and pseudotransitive rules. A disproof ...

Question 1a digital computer has a memory unit with 16 bits

Question 1: A digital computer has a memory unit with 16 bits per word. The instruction set consists of 122 different operations. All instructions have an operation code part (opcode) and an address part (allowing for on ...

Solve the question given belowprove the following statement

Solve the question given below Prove the following statement using Hall's Theorem. For any bipartite graph G=(U, V, E), if every node (either a left node or a right node) has exactly d neighbors, where d is an arbitrary ...

Models of computation assignment -purpose - to improve and

Models of Computation Assignment - Purpose - To improve and consolidate your understanding of regular and context-free languages, finite-state and pushdown automata. To develop skills in analysis and formal reasoning abo ...

Question - design a task or function that will check the

Question - Design a task or function that will check the parity of a word for odd parity. The input to the task/function is a 5-bit word called data_in. If the parity of input data_in is not odd increment an error count ...

Question - design a state machine that will control a

Question - Design a state machine that will control a vending machine. The vending machine has 4 inputs, N, D indicating a nickel or dime was inserted as well as clk and an active high asynchronous reset. The vending mac ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As