Grammar to FSA to C code (Newbie)

Hello everyone,

I am new to C and I have been given a grammar which has to be converted into FSA and C code.

Basically input (a String) is taken and then the output is either Accept or Reject depending upon if the input was or was not in L(G). The grammar is (G is the start and a non-terminal):

Code:

G ---> [ I | aV
V ---> aV | = R
 R ---> aW
W ---> aW | +R | ;G | .

I ---> aC
C ---> aC | >Z
Z ---> aX
X ---> aX | ]G

Note: | means “or’’ and is not part of L(G)
{ a, [, ], +, > } are the Terminal Symbols of G

I did the FSA (pdf attached) and then I worked on the "Algorithm" of how this works and I was wondering if you guys could help me out with seeing if I am on the right track and also if you can suggest anything that should be done differently.

Algorithm

Code:

Get input and then point to the first character of the string and then start with State G.

State G:
	IF a THEN point to next character and goto State V
	ELSE IF [THEN point to next character and goto State I
	ELSE IF print “Reject”

State V:
	IF a THEN point to next character and goto State V
	ELSE IF = THEN point to next character and goto State R
	ELSE IF print “Reject”

State R:	
        IF a THEN point to next character and goto State W
        ELSE IF print “Reject”

State W:
	IF a THEN point to next character and goto State W
	ELSE IF + THEN point to next character and goto State R
	ELSE IF  ; THEN point to next character and goto State G
	ELSE IF print “Reject”

FINAL STATE
	Print “Accept”

State I:
         IF a THEN point to next character and goto State C
         ELSE IF print “Reject”
         
State C:
        IF a THEN point to next character and goto State C
	ELSE IF > THEN point to next character and goto State Z
        ELSE IF print “Reject”

State Z:
        IF a THEN point to next character and goto State X
        ELSE IF print “Reject”

State X:
        IF ] THEN point to next character and goto State G
        ELSE IF print “Reject”

I wanted to see if I am on the right track and also I have K&R and "C Primer Plus" as reference books. Any help would be greatly appreciated.


Thanks.

Having studied your states a bit, i believe it is probably correct, although a bit obscure for a language. Don't hesitate to implement the FSA using goto statements as in your pseudocode. Goto is tailor made for FSA's as proved in this paper.

You can quite easily avoid "goto" in state-machines by using a loop around a switch(state), where each "goto" is replaced with "state = next_state".

--
Mats

I'm seeing a context-free grammar here, yet you want to write an FSA to recognize it? You know that's not possible, right?

Originally Posted by brewbuck

I'm seeing a context-free grammar here, yet you want to write an FSA to recognize it? You know that's not possible, right?

You're right, so it is.
Hmm I should know that. Afterall, my final year research project was writing a genetic algorithm to determine context-free grammar from example sentences.

The pseudocode for W is incorrect. I believe the dot signifies that it may reach the end of the string and be accepted. You shouldn't be saying else if print "reject" either, there's no if about it