Yacc: tokens met verplicht dezelfde inhoud

Thread View: be.comp.programming

6 messages

[T] Back to Threads [V] Tree View [G] Group Articles

6 total messages Started by Jo Vermeulen Mon, 13 Jun 2005 11:26

#1266

Author: Jo Vermeulen
Date: Mon, 13 Jun 2005 11:26

41 lines
2563 bytes

Hallo,

Ik vroeg me af of het mogelijk is in een Yacc grammar (te parsen met 
Bison) af te dwingen dat twee tokens de zelfde inhoud hebben?

Het probleem is te vergelijken met het testen of een tag afgesloten 
wordt in XML/HTML. Bv.

<author>
	<name>John Doe</name>
	...
</author>

Hier moeten we zeker zijn dat de token's tussen <> en </> een identieke 
waarde hebben. Er mag dus niet <auteur></author> staan.

Je kan bv. specifieren dat een "tag" bestaat uit:

(LEQ = '<', GEQ = '>', SLASH = '/', NAME = een geldige tagnaam)

tag : LEQ NAME GEQ content LEQ SLASH NAME GEQ { $$ = new Tag($2, $3); }
     ;

Waarbij je content later nog definieert (bestaat in feite ook uit ��n of 
meerdere tags).

Nu voldoet echter <auteur>...</author> aan die grammar, terwijl dat niet 
zou mogen!

Ik wil nog even herhalen dat mijn probleem niet specifiek over 
XML/HTML-achtige talen gaat, maar over Featherweight Java. Hierbij moet 
de constructor toekenningen precies in de vorm van this.var = var 
bevatten. Een toekenning als this.var = varretje is hierbij ongeldig, en 
zulke fout zou ik graag door de parser laten oplossen.

Alvast bedankt!

mvg,

-- 
Jo Vermeulen <jo@lumumba.luc.ac.be>

Re: Yacc: tokens met verplicht dezelfde inhoud

#1267

Author: Marco van de Voort
Date: Mon, 13 Jun 2005 11:35

21 lines
1856 bytes

On 2005-06-13, Jo Vermeulen <jo@lumumba.luc.ac.be> wrote:
>
> Ik vroeg me af of het mogelijk is in een Yacc grammar (te parsen met 
> Bison) af te dwingen dat twee tokens de zelfde inhoud hebben?

Normaal niet vziw, tenminste niet zoals jij wilt (met variabele tagnamen).
Tenzij GNU Bison extra mogelijkheden heeft boven standaard yacc, om
veelvoudig voorkomende gevallen van semantische analyse aan te pakken.

Dit is deel van de stap achter de eigenlijke parsing, nl semantische
analyse. Vergelijkbaar met het nagaan van type info in een compiler.

Dus je hebt ruwweg:

1 preprocessing  - e.v.t. inlinen, macro expansie e.d.
2 lexing	 - opbreken in tokens.
3 parsing	 - tokens omzetten in parsetree.
4 semantische analyse - parsetree walken en randvoorwaarden controleren.

Deze stappen hoeven natuurlijk niet geheel sequentieel te zijn, maar het kan
ook incrementeel gebruiken.

Re: tokens met verplicht dezelfde inhoud

#1268

Author: Dr.Ruud
Date: Mon, 13 Jun 2005 13:00

23 lines
1562 bytes

Jo Vermeulen schreef:


> Featherweight Java. Hierbij
> moet de constructor toekenningen precies in de vorm van this.var = var
> bevatten. Een toekenning als this.var = varretje is hierbij ongeldig,
> en zulke fout zou ik graag door de parser laten oplossen.

Met oplossen beDoel je corrigeren?

Zonder context-begrenzing, met sed -E:

  /^ *this\.([a-z][a-z0-9_]*) *= *\1 *[,;]/ t ok
  s/^( *this\.)([a-z][a-z0-9_]*)( *= *)([a-z][a-z0-9_]*)(
*[,;])/\1\2\3\2 \/\* was \4 \*\/ \5/
:ok

En overal waar ' *' staat, even '[[:blank:]]*' van maken.

(ongetest)

-- 
Grtz, Ruud

Re: tokens met verplicht dezelfde inhoud

#1269

Author: Jo Vermeulen
Date: Mon, 13 Jun 2005 13:18

37 lines
2519 bytes

Dr.Ruud schreef:
> Jo Vermeulen schreef:
> 
> 
> 
>>Featherweight Java. Hierbij
>>moet de constructor toekenningen precies in de vorm van this.var = var
>>bevatten. Een toekenning als this.var = varretje is hierbij ongeldig,
>>en zulke fout zou ik graag door de parser laten oplossen.
> 
> 
> Met oplossen beDoel je corrigeren?
> 
> Zonder context-begrenzing, met sed -E:
> 
>   /^ *this\.([a-z][a-z0-9_]*) *= *\1 *[,;]/ t ok
>   s/^( *this\.)([a-z][a-z0-9_]*)( *= *)([a-z][a-z0-9_]*)(
> *[,;])/\1\2\3\2 \/\* was \4 \*\/ \5/
> :ok
> 
> En overal waar ' *' staat, even '[[:blank:]]*' van maken.
> 
> (ongetest)

Nee, eigenlijk bedoel ik dat de parser daar een foutmelding bij zou 
moeten geven, m.a.w. aangeven dat het programma niet voldoet aan de 
grammatica. De grammatica zou dit moeten opleggen.

Maar zoals Marco al zei, is het waarschijnlijk gewoon een stap voor de 
semantische analyse.

Bedankt!

mvg,

-- 
Jo Vermeulen

Re: tokens met verplicht dezelfde inhoud

#1270

Author: Jo Vermeulen
Date: Mon, 13 Jun 2005 13:20

37 lines
2475 bytes

Dr.Ruud schreef:
> Jo Vermeulen schreef:
> 
> 
> 
>>Featherweight Java. Hierbij
>>moet de constructor toekenningen precies in de vorm van this.var = var
>>bevatten. Een toekenning als this.var = varretje is hierbij ongeldig,
>>en zulke fout zou ik graag door de parser laten oplossen.
> 
> 
> Met oplossen beDoel je corrigeren?
> 
> Zonder context-begrenzing, met sed -E:
> 
>   /^ *this\.([a-z][a-z0-9_]*) *= *\1 *[,;]/ t ok
>   s/^( *this\.)([a-z][a-z0-9_]*)( *= *)([a-z][a-z0-9_]*)(
> *[,;])/\1\2\3\2 \/\* was \4 \*\/ \5/
> :ok
> 
> En overal waar ' *' staat, even '[[:blank:]]*' van maken.
> 
> (ongetest)

Nee, eigenlijk bedoel ik dat de parser daar een foutmelding bij zou
moeten geven, m.a.w. aangeven dat het programma niet voldoet aan de
grammatica. De grammatica zou dit moeten opleggen.

Maar zoals Marco al zei, is het waarschijnlijk gewoon een stap voor de
semantische analyse.

Bedankt!

mvg,

-- 
Jo Vermeulen

Re: tokens met verplicht dezelfde inhoud

#1271

Author: Marco van de Voort
Date: Mon, 13 Jun 2005 14:17

17 lines
1643 bytes

On 2005-06-13, Jo Vermeulen <jo@lumumba.luc.ac.be> wrote:

>> 
>> En overal waar ' *' staat, even '[[:blank:]]*' van maken.
>> 
>> (ongetest)
>
> Nee, eigenlijk bedoel ik dat de parser daar een foutmelding bij zou
> moeten geven, m.a.w. aangeven dat het programma niet voldoet aan de
> grammatica. De grammatica zou dit moeten opleggen.
>
> Maar zoals Marco al zei, is het waarschijnlijk gewoon een stap voor de
> semantische analyse.

Zie ook Wirth:

http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads