Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Grammar - finding next possible token

Status
Not open for further replies.

JoeRLDuncan

Programmer
Apr 15, 2011
1
CA
Hi, I'm writing a grammar for generating expressions in a scripting language with a scheme like pre-fixing syntax.


So, for example an expression in the script could be something like:

(+ 5 6)

I'm using SWI-Prolog on Ubuntu 10.10 and the DCG notation ('-->') to define the grammar rules.

I have implemented a subset of the intended grammar so far, and it works generally quite well. By querying with an uninstantiated expression variable and empty token list, I can generate every possible expression as a list of tokens.

For example, the token list for the example expression above would be:

['(','+','number','number',')']

What I want to be able to do is use this grammar to sequentially build possible expressions. Basically, I will be using prolog and my grammar to guide users in another program (web-based using PHP) in the creation of grammatically correct expressions in the scripting language.

Users would start an expression and the program would query the grammar to provide a list of options for which token to choose next.

What I need to generate is all the next possible unique tokens, given the current token list.

If I have the token list ['('], I want to retrieve every unique prefix operator in the scripting language (i.e. *, +, -, /, = etc...).

If the token list is ['(','+'], the next possible tokens could be another open bracket or, a 'number' placeholder token.

I know I can query the top level expression rule with an uninstantiated expression and the current token list and this would generate every possible expression that could start with the given token list. But this is a lot of processing and will give many many duplicates for the next immediate token.

If anyone could give me pointers on how I would go about getting only the next immediately possible tokens I would very much appreciate it.

Thanks!
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top