Difference between revisions of "PLC Laboratory 3"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
To simplify the solution, you can use prepared grammar readers (they are prepared for Java and C#). They both read a context grammar from the input and represents it as an object.
 
To simplify the solution, you can use prepared grammar readers (they are prepared for Java and C#). They both read a context grammar from the input and represents it as an object.
 +
* [http://linedu.vsb.cz/~beh01/wiki_data/PLC_lab3_Java.zip Java] - Netbeans 12.6 project
 +
* [http://linedu.vsb.cz/~beh01/wiki_data/PLC_lab3_csharp.zip C#] - VS2022 project
 +
 +
=== Additional guidelines ===
 +
* As a first step, you can compute which non-terminals can be rewritten as an empty word. 
 +
* Informal description, how to compute FIRST and FOLLOW in implementation friendly way is [http://behalek.cs.vsb.cz/vyuka/pjp/cviceni/uloha4/reseni_popis.html Here (only in Czech)]
  
 
== Input specification ==
 
== Input specification ==
  
−
The first line of the input contains a number <code>N</code>. It defines the number of expressions your program should evaluate. These expressions are on next <code>N</code> lines. Each line contains exactly one expression.  
+
The input contains a context free grammar definition. Non-terminals are upper-case letters, terminals are lower-case letters. It composes from several lines; each line ends with the semicolon, and it contains rules for one nonterminal. The line starts with this nonterminal, then there is a colon and it is followed by right hand sides of its rules separated by <code>'|'</code>.
 +
 
 +
There may be also notes in the input, they are written in compose brackets. They have no meaning for the grammar definition.
 +
 
 +
For more detail see the example.
  
 
== Output specification ==
 
== Output specification ==
  
−
For each expression write one line containing the result – the computed value of the expression. If there is any error in the input, write text <code>ERROR</code> instead.
+
For the context free grammar from the input write FIRST sets for the right-hand side of all its rules. Next write computed FOLLOW sets for all grammar non-terminals.  
 +
 
 +
Output’s formatting is not strict, your output should be like the output from the example.
  
 
== Example ==  
 
== Example ==  
Line 23: Line 35:
  
 
* Output
 
* Output
−
Your output can be different, based on your representation of epsilon and the ''end of input'' character.
+
Your output can be different, based on your representation of epsilon and the ''end of input'' character. Also a formatting depends on you.
 
<syntaxhighlight lang="haskell" >
 
<syntaxhighlight lang="haskell" >
−
first[1] = b
+
first[A:bC] = b
−
first[2] = b c d
+
first[A:Bd] = b c d
−
first[3] = c {e}
+
first[B:CC] = c {e}
−
first[4] = b
+
first[B:bA] = b
−
first[5] = c
+
first[C:cC] = c
−
first[6] = {e}
+
first[C:{e}] = {e}
 
follow[A] = d $
 
follow[A] = d $
 
follow[B] = d
 
follow[B] = d
 
follow[C] = c d $
 
follow[C] = c d $
 
</syntaxhighlight >
 
</syntaxhighlight >

Latest revision as of 08:46, 7 March 2023

Computing sets FIRST and FOLLOW

On the input, there is a context free grammar. For this grammar compute sets FIRST (for each right side of given rules) and FOLLOW (for each nonterminal).

To simplify the solution, you can use prepared grammar readers (they are prepared for Java and C#). They both read a context grammar from the input and represents it as an object.

  • Java - Netbeans 12.6 project
  • C# - VS2022 project

Additional guidelines

  • As a first step, you can compute which non-terminals can be rewritten as an empty word.
  • Informal description, how to compute FIRST and FOLLOW in implementation friendly way is Here (only in Czech)

Input specification

The input contains a context free grammar definition. Non-terminals are upper-case letters, terminals are lower-case letters. It composes from several lines; each line ends with the semicolon, and it contains rules for one nonterminal. The line starts with this nonterminal, then there is a colon and it is followed by right hand sides of its rules separated by '|'.

There may be also notes in the input, they are written in compose brackets. They have no meaning for the grammar definition.

For more detail see the example.

Output specification

For the context free grammar from the input write FIRST sets for the right-hand side of all its rules. Next write computed FOLLOW sets for all grammar non-terminals.

Output’s formatting is not strict, your output should be like the output from the example.

Example

  • Input
{Input grammar}
A : b C | B d;
B : C C | b A;
C : c C | {e};
  • Output

Your output can be different, based on your representation of epsilon and the end of input character. Also a formatting depends on you. 

first[A:bC] = b
first[A:Bd] = b c d
first[B:CC] = c {e}
first[B:bA] = b
first[C:cC] = c
first[C:{e}] = {e}
follow[A] = d $
follow[B] = d
follow[C] = c d $
Retrieved from "http://behalek.cs.vsb.cz/wiki/index.php?title=PLC_Laboratory_3&oldid=3342"