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
- a single variable = (single letter)
- function application = (λ-expression)(λ-expression)
- 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
I 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.