Cómo analizar propiedades lógicas ingresadas por el ser humano, p. esto y (eso o lo otro)?

Question

Como parte de un próximo proyecto, me gustaría configurarlo para que cierto objeto de dominio se pueda aplicar a etiquetas o combinaciones de etiquetas.

Me gustaría ser capaz de hacer que los usuarios entran en estas combinaciones en una forma legible por humanos, similares a:

• etiqueta-a y (tag o etiqueta-b-c) -> se aplica etiquetar-a + etiqueta-b o etiqueta-a + etiqueta-c
• etiqueta-d o (etiqueta-e y etiqueta-f) -> se aplica a etiqueta-d o etiqueta-e + etiqueta-f

¿Existe un conjunto de herramientas para realizar este tipo de análisis lógico a partir de una cadena de texto introducido? Podría definir las etiquetas detrás de las escenas con una cierta distinción ({}, [], etc.) para que también puedan analizarse más fácilmente.

Solo me pregunto cuál es la mejor manera de analizar ese texto legible por humanos en esos distintos conjuntos de combinaciones sin que el usuario tenga que ingresar cada combinación específica.

Gracias!

Answer 1

Típicamente esto implica dos pasos: Lexing (abreviatura de análisis léxico) y análisis.

En el primer paso, la cadena de entrada se transforma en una secuencia de elementos léxicos, llamados tokens . Para este fin, es posible declarar un tipo de enumeración de los diferentes tipos de modo, por ejemplo:

public enum TokenType 
{ 
    OpenParenthesis, 
    CloseParenthesis, 
    And, 
    Or, 
    Tag 
} 

y una clase para los tokens:

sealed class Token 
{ 
    public TokenType Type { get; private set; } 
    public string Item { get; private set; } 
    public Token(TokenType type, string item) { Type = type; Item = item; } 
} 

Ahora se escribe un algoritmo que convierte la cadena de entrada, p.ej tag-a and (tag-b or tag-c), en una secuencia de instancias Token. Puede usar expresiones regulares para reconocer los diversos elementos; por ejemplo, @"\s*\(\s*" sería la expresión regular para reconocer entre paréntesis. La secuencia final sería entonces algo como esto:

• new Token(TokenType.Tag, "tag-a")
• new Token(TokenType.And, null)
• new Token(TokenType.OpenParenthesis, null)
• new Token(TokenType.Tag, "tag-b")
• new Token(TokenType.Or, null)
• new Token(TokenType.Tag, "tag-c")
• new Token(TokenType.CloseParenthesis, null)

Una vez que tiene esta secuencia, necesita ejecutar un analizador en él. Hay muchas estrategias para analizar expresiones como estas; para el comienzo, te recomiendo el recursive descent parser.

Usted, por supuesto, necesitará un par de clases para contener el árbol de análisis sintáctico:

abstract class Node { } 
enum BooleanOperator { And, Or } 
sealed class BooleanNode : Node 
{ 
    public BooleanOperator Operator { get; private set; } 
    public Node Left { get; private set; } 
    public Node Right { get; private set; } 
    public BooleanNode(BooleanOperator op, Node left, Node right) 
    { 
     Operator = op; 
     Left = left; 
     Right = right; 
    } 
} 
sealed class TagNode : Node 
{ 
    public string Tag { get; private set; } 
    public TagNode(string tag) { Tag = tag; } 
} 

Y luego un analizador descendente recursivo podría ser algo como esto:

public static Node ParseExpression(Token[] tok) 
{ 
    int i = 0; 
    return parseExpressionBoolOr(tok, ref i); 
} 
private static Node parseExpressionBoolOr(Token[] tok, ref int i) 
{ 
    var left = parseExpressionBoolAnd(tok, ref i); 
    while (tok[i].Type == TokenType.Or) 
    { 
     i++; 
     var right = parseExpressionBoolAnd(tok, ref i); 
     left = new BooleanNode(BooleanOperator.Or, left, right); 
    } 
    return left; 
} 
private static Node parseExpressionBoolAnd(Token[] tok, ref int i) 
{ 
    var left = parseExpressionPrimary(tok, ref i); 
    while (tok[i].Type == TokenType.And) 
    { 
     i++; 
     var right = parseExpressionPrimary(tok, ref i); 
     left = new BooleanNode(BooleanOperator.And, left, right); 
    } 
    return left; 
} 
private static Node parseExpressionPrimary(Token[] tok, ref int i) 
{ 
    if (tok[i].Type == TokenType.OpenParenthesis) 
    { 
     i++; 
     var node = parseExpressionBoolOr(tok, ref i); 
     if (tok[i].Type != TokenType.CloseParenthesis) 
      throw new InvalidOperationException(); // or customised parse exception 
     return node; 
    } 
    else if (tok[i].Type == TokenType.Tag) 
    { 
     var node = new TagNode(tok[i].Item); 
     i++; 
     return node; 
    } 
    else 
     throw new InvalidOperationException(); // or customised parse exception 
} 

Tenga en cuenta que esto es un ejemplo muy simplificado. Sin embargo, es lo más flexible posible: puede ampliar este algoritmo para analizar absolutamente cualquier idioma que desee.