Scribd
Upload
16 views4 pages

LL(1) Syntax Analysis and Parsing Guide

The document discusses transforming a grammar into LL(1) form by addressing left recursion and modifying productions. It describes calculating FIRST and FOLLOW sets and designing a recursive descent parser for the grammar in Python. Key parsing techniques including recursive descent and using FIRST sets are covered, along with error handling and testing the parser.

Uploaded by

Osama RashadAhmed
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views4 pages

LL(1) Syntax Analysis and Parsing Guide

The document discusses transforming a grammar into LL(1) form by addressing left recursion and modifying productions. It describes calculating FIRST and FOLLOW sets and designing a recursive descent parser for the grammar in Python. Key parsing techniques including recursive descent and using FIRST sets are covered, along with error handling and testing the parser.

Uploaded by

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

## Part 2: Syntax Analysis

### Documentation

**1. Transformed Grammar into LL(1):**

**1.1. Ambiguities and Left Recursion:**

The original grammar contains left recursion in `funcDecl`, `statBlock`,

and `variable` productions. These need to be addressed to achieve an

LL(1) grammar.

**1.2. Modified Productions:**

```

funcDecl -> funcHead '{' {varDecl} {statement} '}' ';'

| funcHead EPSILON // Empty statement block

statBlock -> '{' {statement} '}'

| statement

variable -> idnest id {indice}


```

**1.3. LL(1) Grammar:**

The modified grammar is now LL(1). This is because no non-terminal

has two productions with the same FIRST sets.

**2. FIRST and FOLLOW Sets:**

We've calculated the FIRST and FOLLOW sets for each non-terminal in

the modified grammar. Due to space limitations, we'll show a few

examples:

* FIRST(prog) = {'class', 'main'}

* FOLLOW(prog) = {'$'} (end of file)

* FIRST(funcDecl) = {'type', 'EPSILON'} (empty statement block)

* FOLLOW(funcDecl) = {';'}

* FIRST(statement) = {'if', 'for', 'read', 'write', 'return', 'id', '{', 'EPSILON'}

(empty statement)

* FOLLOW(statement) = {';', '}', ')'}

**3. Design:**
The parser is a recursive descent parser. It maintains a stack to keep

track of non-terminals during parsing. The parser function takes the

token stream generated by the scanner as input and attempts to match

productions based on the FIRST sets of non-terminals.

**4. Implementation Tools:**

* Programming Language: Python

Python is chosen for its readability and ease of use for implementing

recursive descent parsing.

**Note:** The complete implementation details (parser class,

functions, error handling) are omitted for brevity, but the key concepts

are provided.

### Key Parsing Techniques:

* **Recursive Descent:** The parser functions call each other based on

the grammar productions.

* **FIRST Sets:** Used to predict the next token type expected during
parsing.

* **Error Handling:**

* Check for mismatched tokens.

* Recover by skipping tokens until a synchronizing token (e.g.,

semicolon) is reached.

### Testing:

* Test cases covering various constructs (control flow, function calls,

variable declarations).

* Cases with errors (missing keywords, semicolons, parentheses, type

mismatches).

This approach provides a foundation for implementing the syntax

analyzer. The specific code implementation will vary depending on the

chosen libraries and desired functionalities.

You might also like