Skip to main content

9. Convert the BNF rules into YACC form and write code to generate abstract


 syntax tree.

Certainly, I can help you with that. To convert BNF rules into YACC form and generate an abstract syntax tree (AST), let's consider a simple arithmetic expression grammar. Here's the BNF grammar for reference:


```

<expr> ::= <term> '+' <expr>

         | <term> '-' <expr>

         | <term>


<term> ::= <factor> '*' <term>

         | <factor> '/' <term>

         | <factor>


<factor> ::= '(' <expr> ')'

          | <number>

```


Now, let's convert these BNF rules into YACC form and include code to generate an abstract syntax tree. The abstract syntax tree can be represented using a struct in C.


```yacc

%{

#include <stdio.h>

#include <stdlib.h>


// Define the structure for the abstract syntax tree nodes

typedef struct ASTNode {

    char operation;         // '+' for addition, '-' for subtraction, '*' for multiplication, '/' for division

    int value;              // For terminals (numbers)

    struct ASTNode* left;   // Left child

    struct ASTNode* right;  // Right child

} ASTNode;


// Function to create a new node for the abstract syntax tree

ASTNode* createNode(char op, int val, ASTNode* left, ASTNode* right) {

    ASTNode* newNode = (ASTNode*)malloc(sizeof(ASTNode));

    newNode->operation = op;

    newNode->value = val;

    newNode->left = left;

    newNode->right = right;

    return newNode;

}

%}


%token NUMBER


%%

expr    : term '+' expr   { $$ = createNode('+', 0, $1, $3); }

        | term '-' expr   { $$ = createNode('-', 0, $1, $3); }

        | term            { $$ = $1; }

        ;


term    : factor '*' term { $$ = createNode('*', 0, $1, $3); }

        | factor '/' term { $$ = createNode('/', 0, $1, $3); }

        | factor          { $$ = $1; }

        ;


factor  : '(' expr ')'    { $$ = $2; }

        | NUMBER          { $$ = createNode('N', $1, NULL, NULL); }

        ;

%%


int main() {

    yyparse();

    // Further processing of the abstract syntax tree can be done here

    return 0;

}


int yylex() {

    // Your lexer code to recognize tokens and return them

}


void yyerror(const char* msg) {

    fprintf(stderr, "Error: %s\n", msg);

}

```


Explanation of key parts:


- `%{ ... %}`: This is the C code block that you can include at the beginning of your YACC file. It defines the abstract syntax tree structure and a function to create nodes.


- `%token NUMBER`: This defines a token named `NUMBER` which is used to represent numeric values.


- `expr`, `term`, `factor`: These are non-terminal rules in the YACC grammar that correspond to the BNF rules. The code following each rule constructs the abstract syntax tree nodes using the `createNode` function.


- `$$`, `$1`, `$2`, `$3`: These variables represent the value associated with different parts of the rule. For example, `$$` represents the value of the entire rule, `$1` represents the value of the first part of the rule, and so on.


- `yyparse()`: This function starts the parsing process.


- `yylex()`: You need to provide your lexer code here to return tokens.


- `yyerror()`: This function is called when an error occurs during parsing.


Remember that this example focuses on demonstrating the conversion of BNF to YACC and the creation of an abstract syntax tree. You would need to integrate this YACC code with your lexer and further process the generated AST for actual use.


Labels:

Comments

Post a Comment

Popular posts from this blog

Program 6: Finding Prime Numbers in a Range

  ** Program 6: Finding Prime Numbers in a Range ** ```assembly .model small .stack 100h .data     start dw 1     end dw 20 .code     main proc         mov ax, start           ; Load 'start' into AX              find_primes:         inc ax                  ; Move to the next number         cmp ax, end             ; Compare with 'end'         jg end_prog             ; Jump to end if AX > 'end'                  mov cx, ax              ; Copy AX to CX   ...
Post a Comment
Read more

4. Write a LEX Program to convert the substring abc to ABC from the given input string.

Sure, here's a LEX program that converts the substring "abc" to "ABC" in the given input string: ```lex %{ #include <stdio.h> %} %% .*abc.*    { printf("%s", yytext); }    /* Match and print everything containing 'abc' */ .         ;                            /* Ignore other characters */ %% int main() {     yylex();     return 0; } ``` Now, let's break down the code line by line: 1. `%{` and `%}`: These are used to enclose C code that should be included in the generated C code. In this case, it includes the standard input-output library (`<stdio.h>`). 2. `.*abc.*`: This is a regular expression pattern. It matches any sequence of characters that contains the substring "abc". 3. `{ printf("%s", yytext); }`: This is the action associated with the pattern. When the pattern is matched, the `yytext` variable contains the matched te...
Post a Comment
Read more

ktu 2019 Cse Complier programing Lab Syllabus

 1Design and implement a lexical analyzer using C language to recognize all valid tokens  in the input program. The lexical analyzer should ignore redundant spaces, tabs and  newlines. It should also ignore comments. 2. Implement a Lexical Analyzer for a given program using Lex Tool. 3. Write a lex program to display the number of lines, words and characters in an input text. 4. Write a LEX Program to convert the substring abc to ABC from the given input string. 5. Write a lex program to find out the total number of vowels and consonants from the given  input string. 6. Generate a YACC specification to recognize a valid arithmetic expression that uses  operators +, – , *,/ and parenthesis. 7. Generate a YACC specification to recognize a valid identifier which starts with a letter  followed by any number of letters or digits.   8. Implementation of Calculator using LEX and YACC  9. Convert the BNF rules into YACC form and write code to generat...
Post a Comment
Read more