Parsing and Parsing table

This PR is for the implementation of the parsing process and implementation of the parsing table.

Remaining tasks

• [x] Parsing table implementation
• [x] Parsing
• [x] Integrate it from the main function with all other modules.
• [x] Write more tests.

Further work

• A module to parse an entire input file.
• A web-app ( Distant future)

Heading

Symbol Table Implementation

Description

This PR is for the implementation of the symbol table.

Remaining Tasks

• [x] Implement all methods
• [x] Fix clang errors
• [x] Fix memory leaks
• [x] Integrate with lexer.

Fixed: Some issues with Lexer

Improved lexer.

Description

Improved Lexer, added namespace jucc::lexer, added more tests. Improved codecov for lexer.cpp towards 100% Updated grammar Parser.

Remaining tasks

• [ ] Review Required

Updating grammar and lexer

Description

Adds improvements and fixes to lexer and parsing grammar. resolves #13

Remaining tasks

• [x] Fix grammar
• [x] Update lexer

Grammar is now ll(1)

Description

grammar.g is updated to a ll(1) context-free-grammar after left-recursion removal and left-factoring.

Changes

1. Removed left recursion for <init_declarator_list> and <block_item_list>
2. Removed <cast_expression>
3. Removed support for assignment operator:

x = 5; // not supported
int x = 5; // supported. grammar limited to declarations

4. Support dropped for the following:

// this is not supported.
if ( <assignment_expression> )
    <statement>
else
    <statement>

// this is supported
if ( <assigment_expression> ) {
    <statements>
} else {
    <statements>
}

resolves #27

BUG REPORT: FIX THE PARSER

OS: Ubuntu (LTS) 20.04 or macOS 10.14+ (please specify version). Compiler: GCC 7.0+ or Clang 8.0+. CMake Profile: all

Steps to Reproduce

inputs

grammar.g

## This is the grammar file for JuCC
## Edit this file to make changes to the parsing grammar
## Epsilon is represented by special string EPSILON

## Terminals
%terminals
else float if int void
( ) { } * + - / % ,
<< >> < > <= >= = == != ;
identifier integer_constant float_constant
main cin cout
%

## Non Terminals
%non_terminals
<primary_expression> <constant> <unary_operator> <unary_expression>
<type_specifier> <multiplicative_expression> <additive_expression>
<shift_expression> <relational_expression> <equality_expression>
<assignment_expression> <expression>
<declaration> <init_declarator_list> <init_declarator>
<initializer> <declarator> <direct_declarator>
<statement> <compound_statement> <block_item_list> <block_item>
<expression_statement> <selection_statement> <program>
%

## Start Symbol
%start
<program>
%

## Grammar for the language
%rules
## Expressions
<primary_expression> : identifier
<primary_expression> : <constant>
<primary_expression> : ( <expression> )
<constant> : integer_constant
<constant> : float_constant
<unary_operator> : +
<unary_operator> : -
<unary_expression> : <primary_expression>
<unary_expression> : <unary_operator> <primary_expression>
<multiplicative_expression> : <unary_expression>
<multiplicative_expression> : <multiplicative_expression> * <unary_expression>
<multiplicative_expression> : <multiplicative_expression> / <unary_expression>
<multiplicative_expression> : <multiplicative_expression> % <unary_expression>
<additive_expression> : <multiplicative_expression>
<additive_expression> : <additive_expression> + <multiplicative_expression>
<additive_expression> : <additive_expression> - <multiplicative_expression>
<shift_expression> : <additive_expression>
<shift_expression> : cin >> <additive_expression>
<shift_expression> : cout << <additive_expression>
<shift_expression> : <shift_expression> << <additive_expression>
<shift_expression> : <shift_expression> >> <additive_expression>
<relational_expression> : <shift_expression>
<relational_expression> : <relational_expression> < <shift_expression>
<relational_expression> : <relational_expression> > <shift_expression>
<relational_expression> : <relational_expression> <= <shift_expression>
<relational_expression> : <relational_expression> >= <shift_expression>
<equality_expression> : <relational_expression>
<equality_expression> : <equality_expression> == <relational_expression>
<equality_expression> : <equality_expression> != <relational_expression>
<assignment_expression> : <equality_expression>
<assignment_expression> : <assignment_expression> = <equality_expression>
<expression> : <assignment_expression>

## Declarations
<declaration> : <type_specifier> <init_declarator_list> ;
<init_declarator_list> : <init_declarator>
<init_declarator_list> : <init_declarator_list> , <init_declarator>
<init_declarator_list> : EPSILON
<init_declarator> : <declarator>
<init_declarator> : <declarator> = <initializer>
<type_specifier> : void
<type_specifier> : int
<type_specifier> : float
<declarator> : <direct_declarator>
<direct_declarator> : identifier
<direct_declarator> : ( <declarator> )
<initializer> : <assignment_expression>

## Statements
<statement> : <compound_statement>
<statement> : <expression_statement>
<statement> : <selection_statement>
<compound_statement> : { <block_item_list> }
<block_item_list> : <block_item>
<block_item_list> : <block_item> <block_item_list> 
<block_item_list> : EPSILON
<block_item> : <declaration>
<block_item> : <statement>
<expression_statement> : <expression> ;
<expression_statement> : ;
<selection_statement> : if ( <expression> ) <compound_statement>
<selection_statement> : if ( <expression> ) <compound_statement> else <compound_statement>

## Main
<program> : <type_specifier> main ( ) <compound_statement>
%

intest1.cc

int main() {
	int x = 1 + 2 + 3 + 4;
	if 1;
}

intest2.cc

int

Expected output:

Some error :anger:

Current Output:

Segmentation fault (core dumped)

Summary

No cout, cin terminals in current grammar, in src/grammar/grammar.g

Solution

The grammar should be able to support cout, cin and should have its respective rules.

Bug Report

Make grammar and lexer consistent with problem statement.

Summary

Some features are still missing in main branch grammar and lexer.

Data Type : integer (int), floating point (float) and void Declaration statements : identifiers are declared in declaration statements as basic data types and may also be assigned constant values (integer of floating) Condition constructs: if, else, nested statements are supported. There may be if statement without else statement. Assignments to the variables are performed using the input / output constructs: cin >> x - Read into variable x cout << x - Write variable x to output Only arithmetic operators {+, -, *, %} and assignment operator `=’ are supported Relational operators used in the if statement are < (less than), > (greater than), == (equal) and != (not equal) Only function is main(), there is no other function. The main() function does not contain arguments and no return statements.

Expected Behavior

Rule for following operators should be present in grammar:

• %

Support for additional tokens:

• >=
• <=
• !=
• +
• -
• *
• /
• %

Solution

Update grammar.g file and lexer.

Left Recursion

Description

• [x] Left Recursion Done
• [ ] Indirect left recursion (if required, after going through the grammar, a decision needs to be made).

Fix: Lexer on Main

Description

Fixing linking and formatting issues in main branch.

Remaining tasks

• [x] Resolve clang-tidy issues
• [x] Add more tests

Bug Report

Summary

Symbol Table bug

Environment

To address the bug, especially if it environment specific, we need to know what kind of configuration you are running on. Please include the following:

OS: Ubuntu (LTS) 20.04 or macOS 10.14+ (please specify version).

Compiler: GCC 7.0+ or Clang 8.0+.

CMake Profile: all

Steps to Reproduce

int main() {
    int x, y;
    cin >> x >> y;
    if (x != 0) {
        if (y > 0) {
            cout << y;
        } else {
            cout << -y;
        }
    }
    float z = 1 + 2 + 3 + 1000/ 50 * 23.2 * (x * y * 10);
    // cout << x << y << z;
    float z0 = 1 + 2 + 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z1 = 1 + 2 - 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z2 = 1 + 2 / 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z3 = 1 + 2 * 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z4 = 1 + 2 % 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z5 = 1 + 2 > 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z6 = 1 + 2 == 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z7 = 1 + 2 != 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z8 = 1 + 2 >= 3 + 1000/ 50 * 23.2 * (x * y * 10);
    float z9 = 1 + 2 <= 3 + 1000/ 50 * 23.2 * (x * y * 10);
    cout << z0 << z1 << z2 << z3 << z4;
    cout << z5 << z6 << z7 << z8 << z9;
}

Expected Behavior

ok

Actual Behavior

jucc: duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y duplicate symbol: x duplicate symbol: y

Keeping your Docker base image up-to-date means you’ll benefit from security fixes in the latest version of your chosen image.

Changes included in this PR

• Dockerfile

We recommend upgrading to ubuntu:rolling, as this image has only 19 known vulnerabilities. To do this, merge this pull request, then verify your application still works as expected.

Some of the most important vulnerabilities in your base image include:

| Severity | Priority Score / 1000 | Issue | Exploit Maturity | | :------: | :-------------------- | :---- | :--------------- | | | 586 | CVE-2021-3996
SNYK-UBUNTU2004-UTILLINUX-2387723 | No Known Exploit | | | 586 | CVE-2021-3996
SNYK-UBUNTU2004-UTILLINUX-2387723 | No Known Exploit | | | 586 | CVE-2021-3995
SNYK-UBUNTU2004-UTILLINUX-2387728 | No Known Exploit | | | 586 | CVE-2021-3995
SNYK-UBUNTU2004-UTILLINUX-2387728 | No Known Exploit | | | 586 | CVE-2021-3995
SNYK-UBUNTU2004-UTILLINUX-2387728 | No Known Exploit |

Note: You are seeing this because you or someone else with access to this repository has authorized Snyk to open fix PRs.

For more information: 🧐 View latest project report

🛠 Adjust project settings

Currently, the CI is only running on ubuntu 20.04. However, JUCC has been tested on macOS with the required dependencies.

Maybe it's time to add a CI and put the project on a temporary hold 🍺 Only bug fixes, no new feature for some time.

Improvement of Symbol Table

Summary

The current implementation of the symbol tables deletes the lexemes on scope end and thus cannot be used for look-up after the lexer phase.

Solution

A better implementation would be an introduction of visibility flags - to be set to false on scope end rather than deleting.

Improve lexer

Summary

The lexer should be able to report the errors in parsing, and also report the line numbers of the input file associated with the same.

Solution

A proper structured error consisting of line number and column number ( if possible ) and the associated error message.