Gramàtiques P45126

Statement

thehtml

Una gramàtica consisteix en regles compostes per una o més produccions i un o més símbols terminals. En aquest exercici suposarem que les produccions comencen amb una lletra majúscula, i que la producció inicial s’anomena I. Per exemple, la gramàtica següent genera totes les parentitzacions correctes (no buides):

→

( )

( I )

I I

En aquest exemple, ( ) es genera aplicant la primera regla, ( ( ) ) es genera aplicant la segona regla i després la primera, ( ) ( ) es genera aplicant la tercera regla i després la primera dues vegades, etcètera.

Suposem que lambda denota un símbol terminal especial buit. Usant aquesta convenció, la gramàtica següent genera totes les paraules que comencen amb a que contenen un nombre parell de as i un nombre senar de bs:

I	→	a SS
SS	→	a PS	\|	b SP
SP	→	a PP	\|	b SS
PS	→	a SS	\|	b PP
PP	→	lambda	\|	a SP	\|	b PS

Feu un programa que escrigui n termes generables amb una gramàtica donada. Si una producció té r regles (numerades de 0 a r − 1), per decidir quina regla triar, feu servir un generador de nombres pseudoaleatoris amb paràmetres m, a, b i s, com està explicat a l’exercici ‍:

int atzar(int r, int m, int a, int b, int& s) { s = (a*s + b)%m; return s%r; }

Entrada

L’entrada comença amb un natural p > 0 que indica el nombre de produccions. Cada producció comença amb el seu nom i el seu nombre de regles r > 0. Cada regla es descriu amb un natural m > 0, seguit de m noms de produccions o de símbols terminals.

L’entrada acaba amb el nombre n de termes que cal generar, seguit dels quatre naturals m, a, b i s que defineixen el generador de nombres pseudoaleatoris.

Sortida

Escriviu n línies, cadascuna amb el terme obtingut aplicant les regles indicades pel generador de nombres pseudoaleatoris. Useu les produccions d’esquerra a dreta dins de cada regla. Cada paraula ha d’estar precedida d’un espai.

Public test cases

Input

1
I 3
  2 ( )
  3 ( I )
  2 I I
8
1007 499 7 400

Output

 ( ( ) ) ( ( ) )
 ( ) ( )
 ( )
 ( )
 ( ( ) )
 ( )
 ( ( ( ) ) ( ) )
 ( ( ) )

Input

5
I 1
  2 a SS
SS 2
  2 a PS
  2 b SP
SP 2
  2 a PP
  2 b SS
PS 2
  2 a SS
  2 b PP
PP 3
  1 lambda
  2 a SP
  2 b PS
15
987 297 15 299

Output

 a b a
 a a a b b b b b a
 a a a a a a a b a
 a a a b b b b b b b a
 a a a a b
 a a b
 a b b b b b a
 a b b a a b a
 a b b a b
 a a a a b
 a a a b a
 a b a
 a a b
 a b a
 a b b b a

Input

6
Obj 2
  1 Sin
  1 Plu
Sin 2
  1 Y
  3 Y de Obj
Plu 2
  1 Z
  3 Z de Obj
Y 3
  2 un jutjat
  1 fetge
  2 un penjat
Z 1
  2 setze jutges
I 2
  3 Plu mengen Obj
  3 Sin menja Obj
5
100207 4517 9843 29253

Output

 setze jutges de un jutjat mengen fetge de un penjat
 un penjat menja un penjat
 un jutjat de fetge menja fetge de un penjat
 un jutjat menja setze jutges
 setze jutges de setze jutges mengen un jutjat

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions