Primeiro e seguir os não-terminais em duas gramáticas

Question

Dado a seguir a gramática

S -> L=L  
s -> L  
L -> *L  
L -> id  

Qual é o primeiro e a seguir para os não-terminais?

Se a gramática for transformada em

S -> L=R  
S -> R  
L -> *R  
L -> id  
R -> L  

Qual será o primeiro e seguirá?

Answer 1

Quando fiz um curso de compilador na faculdade, não entendi primeiro e segui. Eu implementei os algoritmos descritos no Livro do Dragão, mas não tinha idéia do que estava acontecendo. Eu acho que faço agora.

Suponho que você tenha algum livro que dê uma definição formal desses dois conjuntos, e o livro é completamente incompreensível. Vou tentar dar uma descrição informal deles, e espero que isso o ajude a entender o que está em seu livro.

O primeiro conjunto é o conjunto de terminais que você pode ver como a primeira parte da expansão de um não terminal. O conjunto a seguir é o conjunto de terminais que você pode ver após a expansão de um não terminal.

Na sua primeira gramática, existem apenas três tipos de terminais: =, *, e id. (Você também pode considerar $, o símbolo de final de entrada, para ser um terminal.) Os únicos não terminais são S (uma declaração) e L (Um LValue - uma "coisa" a que você pode atribuir).

Pense no primeiro (s) como o conjunto de não-terminais que possam iniciar uma declaração. Intuitivamente, você sabe que não inicia uma declaração com =. Então você não esperaria que isso aparecesse no primeiro (s).

Então, como começa uma declaração? Existem duas regras de produção que definem o que um S parece, e os dois começam com L. Então, para descobrir o que está no primeiro (s), você realmente precisa olhar para o que está no primeiro (L). Existem duas regras de produção que definem como é um LValue: ele começa com um * ou com um id. Então, primeiro (s) = primeiro (l) = { *, id }.

Segue (s) é fácil. Nada segue S Porque é o símbolo inicial. Portanto, a única coisa que se segue é $, o símbolo de final de entrada.

Segue (l) é um pouco mais complicado. Você tem que olhar para todas as regra de produção onde L aparece e veja o que vem depois. Na primeira regra, você vê que = pode seguir L. Então = está em seguida (L). Mas você também percebe nessa regra que há outro L no final da regra de produção. Então, outra coisa que poderia seguir L é qualquer coisa que possa seguir essa produção. Já descobrimos que a única coisa que pode seguir o S A produção é o final de entrada. Então segue (l) = { =, $ }. (Se você olhar para as outras regras de produção, L sempre aparece no final deles, então você fica $ daqueles.)

Dê uma olhada neste Explicação fácil, e por enquanto ignorar todas as coisas sobre ϵ, porque você não possui produções que contêm a corda vazia. Em "Regras para os primeiros conjuntos", as regras nº 1, #3 e #4.1 devem fazer sentido. Em "Regras para seguintes conjuntos", as regras nº 1, #2 e #3 devem fazer sentido.

As coisas ficam mais complicadas quando você tem ϵ em suas regras de produção. Suponha que você tenha algo assim:

D -> S C T id = V  // Declaration is [Static] [Const] Type id = Value
S -> static | ϵ    // The 'static' keyword is optional
C -> const | ϵ     // The 'const' keyword is optional
T -> int | float   // The Type is mandatory and is either 'int' or 'float'
V -> ...           // The Value gets complicated, not important here.

Agora, se você deseja calcular primeiro (d), não pode apenas olhar a primeira (s), porque S pode estar "vazio". Você sabe intuitivamente que o primeiro (d) é { static, const, int, float }. Essa intuição é codificada na regra #4.2. Imagine SCT Neste exemplo como Y1Y2Y3 nas regras de "explicação fácil".

Se você deseja calcular a seguir (s), não pode apenas olhar no primeiro (c), porque isso pode estar vazio, então você também precisa procurar no primeiro (t). Então segue (s) = { const, int, float }. Você obtém isso aplicando "Regras para Follow Sets" #2 e 4 (mais ou menos).

Espero que isso ajude e que você possa descobrir primeiro e seguir a segunda gramática por conta própria.

Se ajudar, R Representa um Rvalue - uma "coisa" a que você não pode atribuir, como uma constante ou literal. Um LValue também pode atuar como um Rvalue (mas não o contrário).

a = 2;  // a is an lvalue, 2 is an rvalue
a = b;  // a is an lvalue, b is an lvalue, but in this context it's an rvalue
2 = a;  // invalid because 2 cannot be an lvalue
2 = 3;  // invalid, same reason.
*4 = b; // Valid!  You would almost never write code like this, but it is
        // grammatically correct: dereferencing an Rvalue gives you an Lvalue.