Unix Programming - Bourne Shell parsing

Author

Bourne Shell parsing

Francois Goudal

2006-02-11, 6:06 pm

Hi,

I'm currently studying computer science in a French High school.
I have a project to implement a bourne shell and at first I have to
write a correct lexer/parser for the bourne shell grammar.
I found a grammar for this in the XSI Reference, that describes the
behaviour of a bourne shell.
But the bison grammar given isn't really good, so I would first like to
know if someone knows about a better reference for a BNF or EBNF Bourne
shell grammar.
By the way, I tried to use the Bison grammar given in this document but
I experienced some problems for writing a flex lexer for it.
The fact is that the scanning of the input depends on the context and I
really don't know how to write a lexer in this condition. I tried using
some sub-lexers (with start conditions of flex) but I didn't succeed.

So I'm currently looking for a context free BNF or EBNF grammar for the
bourne shell language, or a tip on howto implement a context dependant
parser with flex and bison.

Thank's for your help

--
Francois Goudal
Epita promo 2008 - Ing1 - Tresorier Evolutek
francois@goudal.net

Francois Goudal

2006-02-17, 10:40 pm

Francois Goudal wrote:
> Hi,
>
> I'm currently studying computer science in a French High school.
> I have a project to implement a bourne shell and at first I have to
> write a correct lexer/parser for the bourne shell grammar.
> I found a grammar for this in the XSI Reference, that describes the
> behaviour of a bourne shell.
> But the bison grammar given isn't really good, so I would first like to
> know if someone knows about a better reference for a BNF or EBNF Bourne
> shell grammar.
> By the way, I tried to use the Bison grammar given in this document but
> I experienced some problems for writing a flex lexer for it.
> The fact is that the scanning of the input depends on the context and I
> really don't know how to write a lexer in this condition. I tried using
> some sub-lexers (with start conditions of flex) but I didn't succeed.
>
> So I'm currently looking for a context free BNF or EBNF grammar for the
> bourne shell language, or a tip on howto implement a context dependant
> parser with flex and bison.
>
> Thank's for your help
>

No idea ? really ?
I'm asking again cause I'm really blocked because of that.
If a Flex/bison or Shell grammar guru is here, it would really be nice
to help me ;-)

Thank's

--
Francois Goudal
Epita promo 2008 - Ing1 - Tresorier Evolutek
francois@goudal.net

Pascal Bourguignon

2006-02-17, 10:40 pm

Francois Goudal <francois_nospam_@goudal.net> writes:
> No idea ? really ?
> I'm asking again cause I'm really blocked because of that.
> If a Flex/bison or Shell grammar guru is here, it would really be nice
> to help me ;-)

wget ftp://anonymous@ftp.gnu.org/gnu/bash/bash-3.1.tar.gz
tar zxf bash-3.1.tar.gz
emacs bash-3.1/parse.y
# mais pas de lex/flex, ça doit être fait à la main, je suppose.

--
__Pascal Bourguignon__ http://www.informatimago.com/

"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."

Francois Goudal

2006-02-17, 10:40 pm

Pascal Bourguignon wrote:
> Francois Goudal <francois_nospam_@goudal.net> writes:
>
> wget ftp://anonymous@ftp.gnu.org/gnu/bash/bash-3.1.tar.gz
> tar zxf bash-3.1.tar.gz
> emacs bash-3.1/parse.y
> # mais pas de lex/flex, ça doit être fait à la main, je suppose.
>

Oui j'ai deja tente cela mais effectivement, de meme pour zsh d'ailleurs
(qui lui parse et scanne avec du code fait tout a la main d'ailleurs) le
lexeur est a la fin du parser.y, c'est du code fait a la main, et non
pas du flex. Je _dois_ le faire en flex. Cependant je ne vois pas bien
comment faire pour scanner le flux en fonction du contexte avec flex
(probablement avec des sous lexeurs (donc des start conditions) mais je
ne ne vois pas comment, sachant que le contexte est determine dans le
parseur, et qu'on se sert de ce contexte dans le lexeur (le tout sans
variable globale...)

--
Francois Goudal
Epita promo 2008 - Ing1 - Tresorier Evolutek
francois@goudal.net

Pascal Bourguignon

2006-02-17, 10:40 pm

Francois Goudal <francois_nospam_@goudal.net> writes:

> Pascal Bourguignon wrote:
>
> Oui j'ai deja tente cela mais effectivement, de meme pour zsh d'ailleurs
> (qui lui parse et scanne avec du code fait tout a la main d'ailleurs) le
> lexeur est a la fin du parser.y, c'est du code fait a la main, et non
> pas du flex. Je _dois_ le faire en flex. Cependant je ne vois pas bien
> comment faire pour scanner le flux en fonction du contexte avec flex
> (probablement avec des sous lexeurs (donc des start conditions) mais je
> ne ne vois pas comment, sachant que le contexte est determine dans le
> parseur, et qu'on se sert de ce contexte dans le lexeur (le tout sans
> variable globale...)

Avec flex, on utilise la macro BEGIN(etat) pour spécifier l'état du lexer.
On peut l'utiliser aussi bien à partir d'actions flex que d'actions bison.
(Mais c'est certainement plus simple si on le fait seulement a partir
d'actions flex).

Par exemple si on considère la grammaire:

items : item items | item ;
item : IDENT | '[' SPECIFIER ']' ;

/* IDENT : LETTER ; */
/* SPECIFIER : 'C'|'X'|'U'|'/' ; */

on a le problème qu'une lettre CXU peut être considérée comme token
LETTER, ou comme un token specifier. Au niveau du lexer il faudra
donc introduire un état spécial pour traiter les [...].

%x bracket
%%
<INITIAL>{LETTER} { return(tok_ident); }
<bracket>"C"|"X"|"U"|"/" { return(tok_specifier); }
<INITIAL>"[" { BEGIN(bracket); return(tok_open); }
<bracket>"]" { BEGIN(INITIAL); return(tok_close); }

Si il faut vraiment, on peut aussi utiliser BEGIN(...) dans les
actions du parseur.

--
__Pascal Bourguignon__ http://www.informatimago.com/

In a World without Walls and Fences,
who needs Windows and Gates?