C Compiler help

[kaizen3]

Ok, so I am a student of programming, and I need help in my project.

We were asked to create a 'compiler' using C language... This compiler must be able to read a set of lines. The main purpose of the compiler is to be able to solve infix mathematical problems.

Example:

user input:
set a = 5
set b = 10
set c = a + b
print c
output:
15

Now, my problem is, I dont know how to parse the input of the user... Any help would be greatly appreciated.. I am not asking for the whole code.. just some guides. Thank you and god bless.

[msbachman]

Ok, so I am a student of programming, and I need help in my project.

We were asked to create a 'compiler' using C language... This compiler must be able to read a set of lines. The main purpose of the compiler is to be able to solve infix mathematical problems.

Example:

user input:
set a = 5
set b = 10
set c = a + b
print c
output:
15

Now, my problem is, I dont know how to parse the input of the user... Any help would be greatly appreciated.. I am not asking for the whole code.. just some guides. Thank you and god bless.

Have you coded anything on this already? If so include it because I'd much rather critique already made code than think about an algorithm to do this from scratch.

Even if it's total shit I'd suggest doing that and replying back. Leave helpful comments for problem areas too.

You could split the user input into tokens with strtok. Looks like spaces will be natural delimiters.

All in all try to give us something to work with...doesn't have to be perfect but I don't particularly enjoy crafting algorithms at someone's request to save them the time of doing so themselves.

[kaizen3]

thanks for the strtok function.. It helped.

here's what I've done in my spare time today (busy in school T_T)

/*
============================================================================
Name : Compiler.c
Author : John Iniego
Version : 0.01
Description : Compiler
Date Start : July 5, 2010
Date End :
============================================================================
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main(void) {
int i = 0;
int j = 0;
char *temp[20];
char *var[100];
int val[100];
var[0] = "a";
val[0] = 50;
char str[] = "print a"; /*Im testing this input to create the print function*/
char delims[] = " ";
char *result = NULL;
result = strtok(str, delims);

while(result != NULL){
temp[i]=result;
result = strtok(NULL,delims);
i++;
}

if(strcmp(temp[0], "set") == 0){
printf("magseset ng values");
}
else if(strcmp(temp[0], "print") == 0){
printf("print values\n");
while(strcmp(temp[1], var[j]) != 0){
j++;
}
printf("%d", val[j]);
j=0;
}
else{
printf("error!");
}



return(0);
}

/*
* What I am planning is to read the lines, take /n as an endpoint and store the new line on another temp array.
* My problem is, I really dont know how to read and store the value of the line 'set a = <expression>.
* My adviser asked me to use Context-Free Grammar (backus naur form). Any help would be appreciated.
*/




And here is the specs of the program



Simple Compiler: Variable Declaration and Evaluation
In this programming project, we will implement a basic programming language interpreter that handles variable declaration and evaluation. That is, we write a program that tracks all the variables and evaluates expressions based on unambiguous grammar that has the following order of precedence:
% - modulo
* - multiplication
/ - division
+ - addition
- - subtraction
and with the addition of parenthesis (i.e. “(“ and “)”) to override precedence and for grouping. For example, the expression “9 * 8 + 5 * (4 % 3)” evaluates to “52” while “9 * (8 + 5 * 4 % 3)” is equal to “117”.
Simple Natural Programming Language
For this project, we will introduce two keywords essential to our new programming language: set and print.
The set keyword assigns a right-hand expression to the left-hand variable.
set <variable> = <expression>
The print keyword prints to the console the value of a variable.
print <variable>
Variable
The variable used for the programming language may contain up to 20 alphanumeric characters, but may not start with a number.
Syntax Error
Your interpreter should handle syntax errors including, but not limited to, invalid keywords and invalid variable declarations.

[msbachman]

Alright I have a better idea of what's going on here now.

This is just a suggestion, disregard it if you're content with the flow of your code, but I'd do it something to the effect of this for easier manipulation, uses a switch table to segment code based on finding a keyword:

Code: Select all

#include <stdio.h>
#include <string.h>


int main(int argc, char * argv[]) // done out of habit, this is unused in the code
{

char arr[100]; //holds a line of input data

fgets(arr, sizeof(arr), stdin); //now arr has a line of input

int keyword=0; //this will go to the switch table to signify actions dependant upon what is found to be the initial keyword.

if(strstr(arr, "print"))
keyword=1;
else if(strstr(arr, "set"))
keyword=2; //maybe extra keywords if necessary...but be warned, doing it will cause issues if someone names a variable like this "set feprint ...".

switch(keyword)
{
case 1: // print statement
printf("print\n");
break;

case 2:     // if it gets here it means that the word "set" was in the input.  Code for assigning a value to a variable will be needed
printf("set\n");


break;

}
}

That's no code to brag about, I made it in a few minutes.

Honestly, imo this is not a trivial program, so I'll only be able to give you broad suggestions rather than specific snippets to deal with each of the many issues that I might have in writing a program like this.

Here are my thoughts on it.

For starters, there's stuff written on grammar for compliers already. Here's a page that details info on this issue, likely a page that your instructor him/herself has checked out in the past http://www.thefreecountry.com/sourcecode/grammars.shtml

After you get your grammar worked out (imo you're on the right track with the strtok if you want to try to create your own I feel that's capable of working out for you), you'll need to find some way to deal with an unspecified amount of user input.

In my opinion, fgets seems to be a natural choice, because it stops at a newline. You could do it with other read functions as well.

So after that, you have to parse it and determine whether or not it's a "set" or "print".

In terms of setting an unspecified number of variables, I actually am not sure of what to recommend here. You might want to ask your instructor about this if you're as clueless as I am on this. You could set a given number, say seven, possible values and then fill them up as they're used, but I don't think this is an ideal solution.

and with the addition of parenthesis (i.e. “(“ and “)”) to override precedence and for grouping. For example, the expression “9 * 8 + 5 * (4 % 3)” evaluates to “52” while “9 * (8 + 5 * 4 % 3)” is equal to “117”.

My solution for this is to code it up in a separate function entirely. Likely this will grow to be quite big, and it'd make reading the rest of the program much more difficult than it needs to be.

This would be a nightmare to do in a vacuum. Luckily, people have written on it already. http://nickmudge.info/index.php?post=97

As a disclaimer, I think this is a difficult assignment, and it's possible that I'm leading you the wrong way. I hope this helped somewhat regardless; there are better C programmers than me so maybe someone can pick up where I left off.

[fashizzlepop]

Just for the record, this is more of an intrpreter than compiler. It never builds an executable.

[thetan]

Just for the record, this is more of an intrpreter than compiler. It never builds an executable.

Sure, a compiler is a loose term. Really however if you look at the big picture and you apply the same logic, then gcc/g++ is also an interpreter. Now before you say "WAT DAS BS BRO" take a moment to realize that all assembly language is, is just a blue print for an ASIC circuit, one that the CPU interprets to carry out the instructions in the blue print for the circuit.

Also interestingly enough, there are CPUs that can run "interpretted" languages as native code. Theres even modern implementations of ARM CPUs that can process java byte code natively.

The moral of the compiler vs interpreter story is to not get caught up in semantics.

Now back on topic
I <3 writing lexers and parsers! I've made a handful of toy languages out of boredom (standard procedure when you're self studying on lexical analyzation and token based parsers).

I've also made plenty of recursive infix calculators. This is one of my favorite exercises to do when learning a new language.

There are countless ways to implement such a system. They range from the straight forward to the very sophisticated. Ironically, some of the more sophisticated ones are the easier to implement once you understand the basic principals on compilers such as the formation and evaluation of ASTs (abstract syntax trees), building lexical analyzers for token generation and writing recursive grammars with rule precedence in BNF like syntax.

I remember the first time i tried tackling this problem was with C. I kicked my noob ass for a solid week (give me a break i was 15) and i ended up with a shitty/decent solution where i'd parse in accordance to the typical order of operations (yeah my algo was worse then O(n) to be optimistic) recursing (calling the function itself) on encounter of open parenthesis and returning on closed parenthesis.

However, now that i have a good understanding on compiler theory i'm confident enough to hand write simple lexers and LALR (look ahead left to right) type parsers. For more complex parser grammars i'll always try to use a lexer/parser suite such a s flex/bison.

Seeing how your teacher might get some what pissed if you veer from the course material and use something like flex/bison, lemon or even boost.spirit.qi. I'd suggest you do it similar to how i did it my first time and kick your ass stumbling around like a moron over your source for a solid week have fun

[fashizzlepop]

The moral of the compiler vs interpreter story is to not get caught up in

I agree. I was just trying to point out that if he were really making a compiler it would involve much more intricacies and ASM knowledge.

[kaizen3]

Thanks for the help!

Yesterday, my professor asked us to use BISON. He told us that this would be a very useful program in building this compiler/interpreter... Actually it pissed me off, after writing a very long code, I would have to re-do it with this program called Bison.

But really, I appreciated all your help!

I would be posting here again if I encounter more problems using Bison

[thetan]

Thanks for the help!

Yesterday, my professor asked us to use BISON. He told us that this would be a very useful program in building this compiler/interpreter... Actually it pissed me off, after writing a very long code, I would have to re-do it with this program called Bison.

But really, I appreciated all your help!

I would be posting here again if I encounter more problems using Bison

It should make you more appreciative. Also, your teacher said just Bison? As in make your own lexer instead of using flex? thats still kind of annoying

BTW, infix calc is part of the Bison documentation http://www.gnu.org/software/bison/manua ... Infix-Calc

[tgoe]

This is indeed a fun exercise. Check out "The Unix Programming Environment" by Kernighan and Pike. They use an iterative development style tutorial that steps through 6(IIRC) versions of a language called "hoc" that get more and more sophisticated. You go from a simple four function calculator program to a full programming language complete with functions, flow control, named arguments... all running as a simple stack machine in about 1000 lines of code. Sounds to me like your teacher might be taking a similar approach. Get ready to re-implement your language several times