Thread: Grammar to FSA to C code (Newbie)

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    1

    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.

  2. #2
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    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.
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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?

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by brewbuck View Post
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 23
    Last Post: 04-20-2009, 07:35 AM
  2. Enforcing Machine Code Restrictions?
    By SMurf in forum Tech Board
    Replies: 21
    Last Post: 03-30-2009, 07:34 AM
  3. newbie reading code
    By franziss in forum C++ Programming
    Replies: 9
    Last Post: 08-25-2005, 12:18 AM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. Newbie - MFC code from a book in VC++.Net
    By Guardian in forum Windows Programming
    Replies: 2
    Last Post: 04-27-2002, 07:17 PM