Split string into logical pieces (AND, OR, parentheses)?

[camille]

Hello,

has anybody ever written a procedure that is able to receive a string and split it by logical precedence?

E.g.

Code: Select all

string.s = "(k1 != 2 OR ((m1 = 5 AND x1 = 7) OR extension = gif))"

k1, m1, x1 and extension are real variables. 
They need to be resolved into their real value after splitting.

AND has priority over OR and parentheses must be resolved (if present).

This would result in 3 necessary comparisons (in reality more are necessary, like m1 = 5, x1 = 7, etc.)
1. m1 = 5 AND x1 = 7
2. <boolean #True/#False result from 1.> OR extension = gif
3. k1 != 2 OR <boolean #True/#False result from 2.>

Every comparison leads to a #True / #False state (after the belonging variables have been resolved)
The comparison chain would exit once a single #False is one of the results.

E.g.
m1 -> Resolved to 5: 5 = 5 -> #True
x1 -> Resolved to 6: 6 = 7 -> #False
At this point the logical chain can be ended with a break.
If x1 would have been 7, the next comparison would have been:
#True OR extension = gif
Etc.

Any idea how to accomplish something like this with a generic approach?

Merci beaucoup!

[Tenaja]

What you are describing is a parser. There are a few on the forum. There really isn't a generic parser, because every need is different.

[Kiffi]

Code: Select all

EnableExplicit

Define k1 = 2
Define m1 = 6
Define x1 = 5
Define extension.s = "gif"

Define string.s = "(k1 != 2 OR ((m1 = 5 AND x1 = 7) OR extension = 'gif'))"

string = ReplaceString(string, "k1", Str(k1))
string = ReplaceString(string, "m1", Str(m1))
string = ReplaceString(string, "x1", Str(x1))
string = ReplaceString(string, "extension", Chr(34) + extension + Chr(34))

Debug String

UseSQLiteDatabase()
OpenDatabase(0, ":memory:", "", "", #PB_Database_SQLite)
DatabaseQuery(0, "Select " + string)
Debug DatabaseError()
NextDatabaseRow(0)
Debug GetDatabaseLong(0, 0)

[camille]

@Tenaja
Thanks for the hint!

@Kiffi
Thanks! This is the coolest (and shortest) boolean logic parser example ever^^ Great stuff!

[mestnyi]

@Kiffi
Thanks! This is the coolest (and shortest) boolean logic parser example ever^^ Great stuff!

I agree too
but how does it work?

Code: Select all

UseSQLiteDatabase()
OpenDatabase(0, ":memory:", "", "", #PB_Database_SQLite)
DatabaseQuery(0, "Select " + string)
Debug DatabaseError()
NextDatabaseRow(0)
Debug GetDatabaseLong(0, 0)

[TI-994A]

...but how does it work?

SQLite allows the use of the SELECT statement to evaluate expressions without any other database conditions such as FROM or WHERE. But not all databases conform to this.

Code: Select all

UseSQLiteDatabase()
If OpenDatabase(0, ":memory:", "", "")
  
  DatabaseQuery(0, "Select 1 + 1")
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = 2
  
  DatabaseQuery(0, "Select 5 - 2") 
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = 3
  
  DatabaseQuery(0, "Select 9 * 3") 
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = 27
  
  DatabaseQuery(0, "Select 100 / 4") 
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = 25
  
  DatabaseQuery(0, "Select 'apples' = 'apples'") 
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = true = 1
  
  DatabaseQuery(0, "Select 'apples' = 'oranges'") 
  NextDatabaseRow(0)
  Debug GetDatabaseLong(0, 0) ; = false = 0
  
  CloseDatabase(0)
  
EndIf

[Rinzwind]

You leave the actual parsing job to sqlite; bit cheating huh

[Denis]

Hi camille

not a solution but if you want to learn more about parser (analyseur lexicographique/syntaxique etc) :

vidéos (in french) :
Theory of Languages (THL) by Akim Demaille (6 videos of about 4 hours each, these are mathematics for grammars)
THL 1 to THL6, really excellent courses!
Théorie des langages (THL) par Akim Demaille (6 vidéos d'environ 4 heures, ce sont des mathématiques pour les grammaires)
THL 1 à THL6, vraiment d'excellents cours!


THL1 : https://www.youtube.com/watch?v=WbUpN4fHs_k
(others follow on youtube)/les autres suivent sur youtube)

French books (some hard to find/certains difficiles à trouver):
1) Eléments de théorie des Automates par Jacques Sakarovitch
2) Compilation : analyse lexicale et syntaxique, du texte à sa structure en informatique par Romain Legendre & François Schwarzentruber
3) La programmation par syntaxe, des grammaires à la compilation par B. Groc et M. Bouhier
4) Théorie des langages et compilation, brefs résumés de cours et exercices corrigés par Ali Aït el Hadj
5) Introduction à la théorie des langages de programmation par Gilles Dowek & JJ Lévy
6) Langages formels : calculabilité et complexité par Olivier carton
7) Compilateurs : Principes, techniques et outils (2e édition) par de Alfred Aho, Monica Lam & Ravi Sethi

i do prefer n°3 et 1 (soft spot for N°3, which I've had for 30 years.../un faible surtout pour N°3 que j'ai depuis 30 ans...)

[camille]

Hi Denis,

thanks for all the information!

I have to admit, they are a bit over my head currently
A lot of theory...

Camille