Gorodetski Gorodetski - 11 months ago 58
PHP Question

Validating expression using preg_match

Good day! I'm trying to create a program that accepts a Lambda expression from the user and what this program does is to check if it is a Valid Lambda expression.

example - user inputs (λa.abc)a -> then validates

my problem is that my knowledge of Regex function is very limited, I've been using preg_match to solve this but still not much of a progress. any help will be much appreciated.. Thanks :)

Well these are the rules of a valid λ-expression

  1. a single variable = (single letter)

  2. function application = (λ-expression)(λ-expression)

  3. function abstraction = λ(variable).(λ-expression)

This is the code I did with preg_match

if(preg_match("/\((L([a-z])*.(([a-z])*)*)\)/", $getexpression, $match)):
print "Valid!";

does not really work that well

Answer Source

uI must confess that I didn't get too much from your definition of the expressions, since you basically said "an expression is a variable, or a collection of variables".
I'd generally recommend avoiding using the word you're trying to define within the definition itself.

That said, from reading up on Wikipedia and the comments, I think I might have gotten to what could be construed as a working regular expression for this:

// Basic definition: Lambda + letter == variable.
$lVar = 'λ[a-z]';

// Complex definition: Variable, possibly followed by variables,
// and closed with a letter preceeded by a dot or whitespace.
$lExp = "({$lVar}(?:\\.{$lVar})*(?:[ .][a-z]+))";

// Complete definition:
//    1. Only single  expression.
//    2. Or a parameterized expression which may contain
//       the entire pattern recursively.
$lRegEx = "/^$lExp|\\($lExp(?R)\\)\\Z/u";

That being said, I'm not 100% sure this can be tested with a regular expression. At least not fully. This seems to be the sort of thing that you need to write/use a tokenizer for.