Projetar um compilador para uma determinada linguagem envolve, entre outras coisas, especificar quais são os símbolos válidos nesta linguagem, bem como quais são as regras sintáticas que a definem. A linguagem de programação Java é uma linguagem com suporte à orientação a objetos que não permite herança múltipla e que permite que uma classe implemente múltiplas interfaces. A seguir, exibem-se trechos de código sintaticamente válidos na linguagem Java.

Trecho 1:

class A extends B { }

Trecho 2:

class F implements C { }

Trecho 3:

class J extends A implements C, D { }

No trecho 1, cria-se uma classe chamada A que herda de uma classe chamada B. No trecho 2, cria-se uma classe chamada F que implementa uma interface chamada C. No trecho 3, cria-se uma classe chamada J que herda de uma classe chamada A e implementa duas interfaces, chamadas C e D.

Desenvolva uma Gramática Livre do Contexto (GLC) que especifica uma linguagem que não permita herança múltipla e que implemente zero ou mais interfaces, como definido na linguagem de programação Java.

G = ({statement, extends, implements, implements-list, variable, letter, digit}, {a, b, c, d, e, f,
     g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ,,
     {, }}, P, statement)
P = {< statement >  ->  class < variable > < extends > { }
     < extends >  ->  extends < variable > < implements >
                  |   < implements >
     < implements >  ->  implements < implements-list >
                     |   ε
     < implements-list >  ->  < implements-list > , < variable >
                          |   < variable >
     < variable >  ->  < variable > < letter >
                   |   < variable > < digit >
                   |   < letter >
     < letter >  ->  a  |  b  |  c  |  d  |  e  |  f  |  g  |  h  |  i  |  j  |  k  |  l  |  m
                 |   n  |  o  |  p  |  q  |  r  |  s  |  t  |  u  |  v  |  w  |  x  |  y  |  z
     < digit >  ->  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  }