Gramàtiques P45126


Statement
 

pdf   zip

html

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 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@
PPlambda|@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 P33549: “Camins aleatoris”:

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