Thread: Lex Recursive Rule not Possible?

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Lex Recursive Rule not Possible?

    I am trying to implement one Lex program that accepts input of the following forms.

    Code:
    (NOT(NOT(NOT(P))))
    (NOT(P))
    (NOT(NOT(NOT(NOT(P)))))
    And I wrote the following code.

    Code:
    %{
    #include <stdio.h>
    %}
    
    %option noyywrap
    delim 	[ \t\n]
    ws 	{delim}*
    
    awfp   \({ws}[A-Z]{ws}\) 
    
    
    NOTwfp  \({ws}"NOT"{ws}{awfp}{ws}\)
    NOTwfpR \({ws}"NOT"{ws}{NOT}{ws}\)
    NOT     {NOTwfpR}|{NOTwfp}
    
    
    %%
    
    {NOT} { printf("%s\n",yytext); }
    .|\n   		{   /* Ignore all other characters. */   }
    
    %%
    
    
    int main()
    {
        /* Call the lexer, then quit. */
        yylex();
        return 0;
    }
    I am getting the following error.

    Code:
    flex scanner push-back overflow

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Lex is generally not where you handle recursive rules. That's for grammar tools like Yacc. For the simple example of (NOT(P)), lex should simple break your input into tokens like TOK_LPAREN TOK_NOT TOK_LPAREN TOK_IDENTIFIER TOK_RPAREN TOK_RPAREN.
    Last edited by anduril462; 01-14-2012 at 12:09 AM.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Regular expressions are incapable of describing arbitrarily nested structures. Just one of those fundamental truths, not a shortcoming of lex.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Yes exactly. I was trying to implement CFG in Lex which is very foolish to think about.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  2. Simpson's rule and Trapezoidal rule from fixed array
    By timwonderer in forum C++ Programming
    Replies: 1
    Last Post: 12-02-2010, 03:14 PM
  3. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 10:13 AM
  4. merge sort: recursive is fasfter than non-recursive
    By rio_cat in forum C Programming
    Replies: 8
    Last Post: 12-04-2006, 12:52 AM
  5. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM