LL1Checker

LL1Checker is a tool for verifying if a grammar is LL(1) and for validating whether an input string belongs to the language generated by the grammar. The grammar is read from a file.

📖 Table of Contents

1. Project Status
2. Requirements
3. Run the Program
4. Considerations
5. Structure of grammar.txt
6. Want to Contribute?
7. Compilation

🚀 Project Status

This project is complete, with all essential functionalities implemented and tested with various grammars. It is now in maintenance mode for potential enhancements or bug fixes. If you encounter any issues or unexpected interpretations, please open an issue and include relevant details. Contributions for further improvement are welcome!

📋 Requirements

• Flex: Required to generate and compile the lexer file sudo apt install flex in Debian based distros. If you use Windows, winflexbison is required and in your PATH
• gcc: Used for compiling the generated lex file.

▶️ Run

You can run the program as follows:

./ll1 <GRAMMAR_FILENAME>

• Checks if the provided grammar is LL(1).
• If the grammar has conflicts, displays the LL(1) table with conflicts for debugging.

./ll1 <GRAMMAR_FILENAME> <INPUT_FILENAME>

• Checks if the provided grammar is LL(1) and validates if the input conforms to the grammar.
• If the grammar is not LL(1), it displays the LL(1) table with conflicts.

Optional Verbose Mode

To enable additional debug information, including the full LL(1) table and the input content:

./ll1 <GRAMMAR_FILENAME> <INPUT_FILENAME> -v

In verbose mode, the program will:

• Display the entire LL(1) table, including any conflicts if the grammar is not LL(1).
• Print the contents of <INPUT_FILENAME> for easy reference before parsing.

Error Handling: If <GRAMMAR_FILENAME> or <INPUT_FILENAME> do not exist or cannot be opened, the program will print an error and exit.

📌 Considerations

• The default end of line character is $. This can be changed using the instruction set EOL char (...).
• The end-of-line character can be omitted in the grammar (see grammar.txt), but it's recommended to add a first rule, such as S -> E EOL, where S is the axiom.
• For terminal symbols, note that order matters. If two regexes have common elements, place the more specific one first, as in the example:

terminal WH while;
terminal WORD [a-zA-Z][a-zA-Z]*;

📄 Structure of grammar.txt

The grammar file has two sections separated by ;: symbol definition and grammar definition.

Symbol definition

start with S;

You should write the last line to designate S as the axiom. The terminal symbols follows the following structure: terminal <IDENTIFIER> <REGEX>; (like a variable!). The <IDENTIFIER> should adhere to the following regex pattern: [a-zA-Z_\'][a-zA-Z_\'0-9]*. An example of the first section would be:

terminal a a;
start with S;
;

Grammar definition

The grammar follows the following structure:

S -> A$;
A -> aaA;
A ->;
;

The line A->; represents an empty production. So, our grammar.txt would be:

terminal a a;
start with S;
;
S -> A$;
A -> aaA;
A ->;
;

This grammar generates the following language: L(G) = {aa, aaaa, aaaaaa, ...}, that is, a language with an even number of 'a'. And in input.txt file, you place the line you want to check.

🤝 Want to Contribute?

To get started, you'll need the following:

• Boost Libraries: Make sure you have the following installed:
  • boost_filesystem 📁
  • boost_system ⚙️

Feel free to reach out if you have any questions or suggestions! 😊

🛠️ Compilation

A Makefile is provided, so, run make to compile the project.