Given a routing table in rails, it is possible to generate a state table for recognizing URI paths. We'll use journey to parse routes, and a proof of concept library compiler to generate the state table.
We'll work assuming a routes file that looks like this:
AppTemplate::Application.routes.draw do
resources :articles
end
A resource in Rails will create four unique patterns for matching the path:
/articles(.:format)
/articles/new(.:format)
/articles/:id/edit(.:format)
/articles/:id(.:format)
We can use journey obtain a parse tree for each route and generate a graph:
require 'compiler'
parser = Journey::Definition::Parser.new
ast = parser.parse '/articles(.:format)'
puts ast.to_dot
If we graph the generated parse tree, it looks like this:
We can walk the parse tree for a route and convert an NFA table for that route. After obtaining this table, we can output a dot file:
require 'compiler'
parser = Journey::Definition::Parser.new
ast = parser.parse '/articles(.:format)'
to_nfa = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast
puts nfa_tree.to_dot
Feed the dot file through Graphviz and we get this:
The circled node indicates an "accepting" state. If our state machine ends on that state, we know we have a match.
We can convert our NFA table to a DFA table, reducing states and eliminating nil transitions. Finally, output our DFA table as a dot file:
require 'compiler'
parser = Journey::Definition::Parser.new
ast = parser.parse '/articles(.:format)'
to_nfa = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast
nfa = Compiler::NFA.new nfa_tree
dfa_tree = nfa.dfa_tree
puts dfa_tree.to_dot
Feed this dot file through Graphviz:
We now have vastly fewer states, and our table is deterministic. Again, the double circled states are states where we know we have a match.
We create parse trees for all routes generated by the resources
line and combine them using an OR
node. We'll output dot files for the combined NFA and DFA state tables:
require 'compiler'
routes = [
'/articles(.:format)',
'/articles/new(.:format)',
'/articles/:id/edit(.:format)',
'/articles/:id(.:format)',
]
parser = Journey::Definition::Parser.new
# Parse all routes
asts = routes.map { |r| parser.parse r }
# Combine routes under an OR node
ast = Journey::Definition::Node.new(:OR, asts)
to_nfa = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast
File.open('nfa.dot', 'wb') { |f| f.write nfa_tree.to_dot }
nfa = Compiler::NFA.new nfa_tree
dfa_tree = nfa.dfa_tree
File.open('dfa.dot', 'wb') { |f| f.write dfa_tree.to_dot }
The resulting NFA table looks like this:
Finally we can view the resulting DFA table:
Possible next steps could be:
- Output state tables that Racc can use for simulation
- Write our own simulator for this state table
- Generate a regular expression from the DFA
Improvements:
- Make journey directly output the NFA from the grammar
Thanks for this! I'm trying to get this working with the new version of Journey is difficult (without really understanding Journey enough). I've updated the gist and complier, but it looks like
Node
was moved toJourney::Nodes::Node
which has an initializer taking only the:left
argument. So I can't figure out how to combine the routes under the OR node because population of the enumerable is not apparent. Ideas.