Standalone problem to test syntax rules

Standalone problem to test syntax rules

[Bean]

Hi,

I have written a small problem to test my parse.y, to compile, use the
following commands:

bison -d -p grub_script_yy -b grub_script parser.y 
gcc -oparser parser.c lexer.c grub_script.tab.c

After compilation, run parser

./parser

Just enter the commands after '##', and the syntax tree associtaed with it
will be displayed.

The program support option - , which is used to disable prompt '##' and '>>'.
This is useful when inputting from files:

./parser - < input_file

Some example:

## aa "aa${BB}cc" "\
>dd"
CMD
  TEXT
    STR  "aa"
  TEXT
    STR  "aa"
    VAR  "BB"
    STR  "cc"
  TEXT
    STR  "dd"

## if aa; then
> bb dd$cc
> fi
IF
  CMDS
    CMD
      TEXT
        STR  "aa"
  CMDS
    CMD
      TEXT
        STR  "bb"
      TEXT
        STR  "dd"
        VAR  "cc"

## function foo {
> set AA=1
> if aa; then bb; else cc; fi
> }
FUNC
  TEXT
    STR  "foo"
  CMDS
    CMD
      TEXT
        STR  "set"
      TEXT
        STR  "AA=1"
    IF
      CMDS
        CMD
          TEXT
            STR  "aa"
      CMDS
        CMD
          TEXT
            STR  "bb"
      CMDS
        CMD
          TEXT
            STR  "cc"

The reason why I like to use binary tree is:

1. Standard data type for all script elements, only one set of function is
needed to manipulate the structure.

2. Enumeration and deallocation is simpler. Instead of using switch, we
can enumerate the tree using its two branch, child and next.

I also figure out how to release memory when syntax error occurs. When a
node is first created using grub_script_newnode, it's added to a linked
list state->free_list. When it's referenced, it's moved from the linked
list to the branch of a tree. If the whole script is parsed, all nodes
will be moved to the final tree, but if it fails at some point, partial
built element can be found in the free list. This way, we can also keep
track of nodes allocated. For example, consider this command:

## aa bb

commands:	command
		{
		  $$=$1;
		}
		| commands command
		{
		  $$=grub_script_catnode(state, $1, $2);
		}

Using the second rule, node bb is moved out of free list and move to the next
branch of aa. Now the free list look like this:

root => 0

free_list => aa => 0
             |
             bb

script:		commands '\n'
                {
                  state->root=grub_script_getnode(state, $1);
                }

Now aa is moved out of free list:

root => aa => 0
        |
        bb

free_list => 0

In any given time, all nodes can be found in either root or free_list.

The latest version of parser support error recovery, for example:

## fi ; aa ; bb ; fi ; ee
syntax error
invalid command
syntax error
invalid command
== TREE BEGIN ==
CMD
  TEXT
    STR  "aa"
CMD
  TEXT
    STR  "bb"
CMD
  TEXT
    STR  "ee"
== TREE END ==

-- 
Bean

Re: Standalone problem to test syntax rules

[Bean]

[-- Attachment #1: Type: text/plain, Size: 58 bytes --]

I forget to include the attachment. Here is it.

-- 
Bean

[-- Attachment #2: parser.tar.gz --]
[-- Type: application/octet-stream, Size: 5524 bytes --]

Re: Standalone problem to test syntax rules

[Marco Gerards]

Bean <bean123@126.com> writes:


Hi Bean,

> I have written a small problem to test my parse.y, to compile, use the
> following commands:
>
> bison -d -p grub_script_yy -b grub_script parser.y 
> gcc -oparser parser.c lexer.c grub_script.tab.c
>
> After compilation, run parser
>
> ./parser
>
> Just enter the commands after '##', and the syntax tree associtaed with it
> will be displayed.
>
> The program support option - , which is used to disable prompt '##' and '>>'.
> This is useful when inputting from files:
>
> ./parser - < input_file
>
> Some example:
>
> ## aa "aa${BB}cc" "\
>>dd"
> CMD
>   TEXT
>     STR  "aa"
>   TEXT
>     STR  "aa"
>     VAR  "BB"
>     STR  "cc"
>   TEXT
>     STR  "dd"

[...]

> The reason why I like to use binary tree is:
>
> 1. Standard data type for all script elements, only one set of function is
> needed to manipulate the structure.
>
> 2. Enumeration and deallocation is simpler. Instead of using switch, we
> can enumerate the tree using its two branch, child and next.
>
> I also figure out how to release memory when syntax error occurs. When a
> node is first created using grub_script_newnode, it's added to a linked
> list state->free_list. When it's referenced, it's moved from the linked
> list to the branch of a tree. If the whole script is parsed, all nodes
> will be moved to the final tree, but if it fails at some point, partial
> built element can be found in the free list. This way, we can also keep
> track of nodes allocated. For example, consider this command:

You are right that it has advantages.  But I prefer using an Abstract
Syntax Tree.  It is used a lot in most literature on parsers, clean
and easy to understand.

The disadvantage is that you need a separate free routine for each
kind of node.  But heck, we can even generalize this!

I agree there is a lot of room for improvement.  But stepping away
from using ASTs is not the way to go in my opinion.

--
Marco

Re: Standalone problem to test syntax rules

[Bean]

On Sun, Jul 22, 2007 at 03:06:49PM +0200, Marco Gerards wrote:
> You are right that it has advantages.  But I prefer using an Abstract
> Syntax Tree.  It is used a lot in most literature on parsers, clean
> and easy to understand.
> 
> The disadvantage is that you need a separate free routine for each
> kind of node.  But heck, we can even generalize this!
> 
> I agree there is a lot of room for improvement.  But stepping away
> from using ASTs is not the way to go in my opinion.

Using AST or binary tree is only a matter of choice. If you think AST is
better, I will modify the code to use AST.

Would you take a look at the program, especially the error recover rules. 
I think it can handle all situation, but you never know until it's fully
tested.

-- 
Bean

Re: Standalone problem to test syntax rules

[Marco Gerards]

Bean <bean123ch@gmail.com> writes:

> On Sun, Jul 22, 2007 at 03:06:49PM +0200, Marco Gerards wrote:
>> You are right that it has advantages.  But I prefer using an Abstract
>> Syntax Tree.  It is used a lot in most literature on parsers, clean
>> and easy to understand.
>> 
>> The disadvantage is that you need a separate free routine for each
>> kind of node.  But heck, we can even generalize this!
>> 
>> I agree there is a lot of room for improvement.  But stepping away
>> from using ASTs is not the way to go in my opinion.
>
> Using AST or binary tree is only a matter of choice. If you think AST is
> better, I will modify the code to use AST.

The code already uses an AST.  Or what do you mean?

If I am not mistaken, you are going over parser.y to make it work with
more situations and to introduce proper error handling.  Or am I
mistaken?

> Would you take a look at the program, especially the error recover rules. 
> I think it can handle all situation, but you never know until it's fully
> tested.

In the tarball?

--
Marco

Re: Standalone problem to test syntax rules

[Bean]

On Sun, Jul 22, 2007 at 06:21:18PM +0200, Marco Gerards wrote:
> The code already uses an AST.  Or what do you mean?

I mean the test program.

> If I am not mistaken, you are going over parser.y to make it work with
> more situations and to introduce proper error handling.  Or am I
> mistaken?

There is a lot of change. The basic idea is that commands should be seperated
by either ';' or '\n', followed by zero or more '\n'.

delimiter: '\n'
	   | ';'
	   | delimiter '\n'

> 
> > Would you take a look at the program, especially the error recover rules. 
> > I think it can handle all situation, but you never know until it's fully
> > tested.
> 
> In the tarball? 

Yes.

-- 
Bean

Re: Standalone problem to test syntax rules

[Marco Gerards]

Bean <bean123ch@gmail.com> writes:

>> In the tarball? 
>
> Yes.

Could you send the files to the list as attachments?  Or whatever is
relevant.  tarballs on a mailinglist are very inconvenient. :-/

--
Marco

Re: Standalone problem to test syntax rules

[Gregg Levine]

On Nov 10, 2007 1:43 PM, Marco Gerards <mgerards@xs4all.nl> wrote:
> Bean <bean123ch@gmail.com> writes:
>
> >> In the tarball?
> >
> > Yes.
>
> Could you send the files to the list as attachments?  Or whatever is
> relevant.  tarballs on a mailinglist are very inconvenient. :-/
>
> --
> Marco
>
>
>
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
>

Hello!
I agree! Those things on a list are driving people that way on the
LinuxBIOS list. While I won't name names, I can tell that the
responsible party is leaning towards conventional patches.

There is as it happens a number of places where a blob can be stored
for access by us, should you not be able to host them locally. Of
course I can't recall them, but certainly someone on this list can do
that.
-- 
Gregg C Levine gregg.drwho8@gmail.com
"This signature was once found posting rude
 messages in English in the Moscow subway."