From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with archive (Exim 4.43) id 1I5mZV-0003hm-Px for mharc-grub-devel@gnu.org; Tue, 03 Jul 2007 13:53:53 -0400 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1I5mZT-0003hh-TM for grub-devel@gnu.org; Tue, 03 Jul 2007 13:53:51 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1I5mZT-0003hV-BO for grub-devel@gnu.org; Tue, 03 Jul 2007 13:53:51 -0400 Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1I5mZT-0003hS-6c for grub-devel@gnu.org; Tue, 03 Jul 2007 13:53:51 -0400 Received: from m15-111.126.com ([220.181.15.111]) by monty-python.gnu.org with smtp (Exim 4.60) (envelope-from ) id 1I5mZR-0004q3-Kn for grub-devel@gnu.org; Tue, 03 Jul 2007 13:53:50 -0400 Received: from localhost (unknown [121.201.47.51]) by smtp1 (Coremail) with SMTP id wKjJCxIA8ngljYpGdqldCw==.56604S2; Wed, 04 Jul 2007 01:53:42 +0800 (CST) Date: Wed, 4 Jul 2007 01:53:16 +0800 From: Bean To: The development of GRUB 2 Message-ID: <20070703175316.GA2306@ws3.vdp.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.13 (2006-08-11) X-Coremail-Antispam: 1U3Yxn0WfASr-VFAUDIcSsGvfJTRUUUjVIY02Avz4vE14v_Gw AFxVCF77xC6IxKo4kEV4ylIxAIcVC2z280aVAFwI0_Jr0_Gr1lnxkEFVAIw20F6cxK64vI FxWlx4CE17CEb7AF67AKxVWUJVWUXwCjxxvEw4Wle4C267I2x7xF54xIwI1lYx0E2Ix0cI 8IcVAFwI0_Jr0_Jr4l4x8a6c8ajcxJMcIj6I8E87Iv67AKxVWUJVW8JwAFxVCaYxvI4VCI wcAKzIAtMxkI7II2jI8vz4vEwIxGrwCI42IY6I8E87Iv6xkF7I0E14v26r1j6r4UM7AC8V AFwI0_Jr0_Gr1ln4vEIxA26c8GOVWUur1xXr4lb4IE77IF4wAFIxvE14AKwVWUJVWUGwAq x4xG64xvF2IEw4CE5I8CrVC2j2Wlc7Ca8VAvwVAKO7xYrVA2I41lc7Ca8VAvwVA2a4k0Fc xrMxkFs20EY4vE77kJM7k0a2IF6F4Un29KB7ZKAUJUUUUUnxnvy29KBjDU0xZFpf9x07by HUgUUUUU129KBjvJXoW7ur4DWr1Utry5uw13Cry3urg_yoW8Kry7prWrW34ktrZ7Xws5Ww 4kur48ury8Xan0krZrKrWrJryqqFWYqa4Sy34IkF4S9ry5ur1Uur129rs0vayUKw1DArD= = X-detected-kernel: Linux 2.4-2.6 Subject: Standalone problem to test syntax rules X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: The development of GRUB 2 List-Id: The development of GRUB 2 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 03 Jul 2007 17:53:52 -0000 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