Bottom-up parser and semantic analysis for the dot grammar
$10-30 USD
Paid on delivery
Use SableCC bottom-up parsing tool to construct a parser for the dot grammar. You can find grammer at [url removed, login to view]
The parser should accept the following dot code:
digraph G {
main [shape=box];
main -> parse [weight=8];
parse -> execute;
main -> init [style=dotted];
main -> cleanup;
execute -> make_string;
init -> make_string;
main -> printf [style=bold,label="100 times"];
make_string [label="make a\nstring"];
node [shape=box,style=filled,color=".7 .3 1.0"];
execute -> compare;
}
Then use that tool to construct an intermediate representation of the input graph. The choice of intermediate representation could be a graph, tree, or basically any other representation that you want.
Need the grammar file (that you feed into your parser tool) along with some evidence that the parser tool accepts your grammar and produces a parser. Also need the code that you had to write to generate an intermediate representation (if the tool doesn't generate the parse tree or AST by itself).
Use the intermediate representation (e.g., parse tree) that either your top-down parser or your bottom-up parser generates, and perform some kind of semantic analysis. The specific type of analysis is up to you. At minimum, it should involve a well-structured tree walker navigating through the tree, applying semantic rules to the input. Examples of what you could do include:
- Check if the input graph is acyclic or not.
- Check if the input graph is a connected graph or is it in disconnected pieces.
- Is the input graph fully connected (all nodes connected to all other nodes).
- Write a shortest path algorithm that takes two nodes as input, and finds the shortest path through the graph between the two nodes.
- Assume the input graph represents a program flow graph (you may have to recreate a sample input) and calculate its cyclomatic complexity.
- Given an unordered set of A -> B; statements as input, assume the input describes a tree, and build a tree data structure from the input (this is equivalent to building an AST).
- These are just examples, you can choose something else if you want.
Turn in a description of what kind of semantic analysis you are performing, a description of the intermediate representation that your parser generates, your semantic analysis/tree walking code, and a brief description (could be a comment in the code) of basically how your analyzer does its work.
Project ID: #6067086
About the project
3 freelancers are bidding on average $743 for this job
hello am redhet certified software engineer and i know i can do this task easily i am ready to start now have a look to my reviews thanks