C-Language-Parser

A complete Parser for C-Language using Yacc.

INTRODUCTION

---

A parser is a compiler or interpreter component that breaks data into smaller elements for easy translation into another language. A parser takes input in the form of a sequence of tokens or program instructions and usually builds a data structure in the form of a parse tree or an abstract syntax tree. The main job of a parser for a programminning language is to read the source program and discover its structure. Lex and Yacc can generate program fragments that solve this task. The task of discovering the source structure again is decomposed into subtasks:

1. Split the source file into tokens (Lex).
2. Find the hierarchical structure of the program (Yacc).

** Lex - A Lexical Analyzer Generator:**

Lex helps write programs whose control flow is directed by instances of regular expressions in the input stream. It is well suited for editor-script type transformations and for segmenting input in preparation for a parsing routine.

Lex source is a table of regular expressions and corresponding program fragments. The table is translated to a program which reads an input stream, copying it to an output stream and partitioning the input into strings which match the given expressions. As each such string is recognized the corresponding program fragment is executed. The recognition of the expressions is performed by a deterministic finite automaton generated by Lex. The program fragments written by the user are executed in the order in which the corresponding regular expressions occur in the input stream.

Yacc - Yet Another Compiler-Compiler:

Yacc is a computer program for the Unix operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to BNF called Production Rules.

The input to Yacc is a grammar with snippets of C code (called "actions") attached to its rules. Its output is a shift-reduce parser in C that executes the C snippets associated with each rule as soon as the rule is recognized. Typical actions involve the construction of parse trees. Yacc works in conjuction with a lexical analyser (Lex) in order to tokenize the input code and return the tokens.

This parser is designed such that it detects the SYNTACTIC authenticity of the source program in C - Language and displays the line no. in which there is a syntax error is any, supported by comments to help debug the program. It does not take into account the semantic correctness of the source program.

REQUIREMENTS & INSTALLATION

---

These requirements are for users running Debian based Operating Systems like Ubuntu/Fedora. One needs Flex(lex) and Bison(upward compatible with yacc) for lexical analyzer generator and parser generator.

To install flex and yacc in Ubuntu: 1. sudo apt-get install flex 2. sudo apt-get install bison

To install flex and yacc in Fedora: 1. sudo yum install flex 2. sudo yum install bison

Steps to execute the project:

1. First Compile yacc program

    yacc -v project.y
   

   It will generate 3 files- y.tab.c , y.tab.h and y.output

2. Compile lex file

    lex project.l
   

   It will generate lex.yy.c file

3. Run the following commands

   • gcc -o a.out y.tab.c lex.yy.c -lfl -lm
   • ./a.out < inp

OR

Simply execute the shellscript to automate, Run

• chmod +x runproject.sh
• ./runproject.sh

Outputs:

• If the given program is syntactic correct the output displayed on the terminal - Parsing Successful

• If the given program is synatactically incorrect, the following is message is produced supported by debugging comments stating the incorrect token which is encountered along the legit token that is expected by a syntactically correct program such as the following

  Parsing Failed Line Number: 19 syntax error, unexpected '{', expecting ';' or ','

FAQ

---

Q. I have given as input a C program which is syntactically correct but contains lines which use the values of variables which have either been uninitialised or undeclared. Will this code parse successfully ?

A. Yes, such type of program will parse successfully as this parser only checks the syntactical correctness of the program and not the semantics.

Q. Can the variable declaration statement be placed anywhere in the code block and still parse successfully ?

A. No, declaration statements (e.g. int a = 2;) have to be placed only at the starting of a code block.