Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Mun

By: a guest on Jul 22nd, 2010  |  syntax: C#  |  size: 12.30 KB  |  views: 230  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4. using System.Text;
  5. using System.Text.RegularExpressions;
  6.  
  7. namespace QueryParser
  8. {
  9.         /// <summary>
  10.         ///     This class is used to parse a user entered string into a query
  11.         ///     for use in a SQL statement with the CONTAINS clause for full-text searching
  12.         /// </summary>
  13.         /// <remarks>
  14.         ///     This query parser is based heavily on code originally written by Robert Dominy (http://dev.angusog.com/).
  15.         ///     It was originally in server-side JScript, and converted to C# for use in ASP.NET by Munsifali Rashid.
  16.         /// </remarks>
  17.         public class UserQueryParser
  18.         {
  19.                 #region Constructor
  20.  
  21.                 static UserQueryParser()
  22.                 {
  23.                         m_BuiltInTokens["and"] = new Token(TokenType.AndOperator, "AND");
  24.                         m_BuiltInTokens["or"] = new Token(TokenType.OrOperator, "OR");
  25.                         m_BuiltInTokens["near"] = new Token(TokenType.NearOperator, "NEAR");
  26.                         m_BuiltInTokens["not"] = new Token(TokenType.NotOperator, "NOT");
  27.                         m_BuiltInTokens["("] = new Token(TokenType.LeftParenthis, "(");
  28.                         m_BuiltInTokens[")"] = new Token(TokenType.RightParenthis, ")");
  29.                 }
  30.  
  31.                 #endregion
  32.  
  33.                 #region Private variables
  34.  
  35.                 private string m_Error = string.Empty;
  36.                 private readonly List<Token> m_Tokens = new List<Token>();
  37.                 private static readonly List<String> m_NoiseWords = new List<string>();
  38.                 private static readonly Dictionary<String, Token> m_BuiltInTokens = new Dictionary<string, Token>();
  39.  
  40.                 #endregion
  41.  
  42.                 #region Accessors
  43.  
  44.                 public string Error
  45.                 {
  46.                         get
  47.                         {
  48.                                 return m_Error;
  49.                         }
  50.                 }
  51.  
  52.                 public static List<string> NoiseWords
  53.                 {
  54.                         get
  55.                         {
  56.                                 return m_NoiseWords;
  57.                         }
  58.                 }
  59.  
  60.                 #endregion
  61.  
  62.                 /// <summary>
  63.                 /// Gets the tokens in a string ready for use in a SQL query with the CONTAINS clause
  64.                 /// </summary>
  65.                 public string GetSqlQuery()
  66.                 {
  67.                         StringBuilder sb = new StringBuilder();
  68.  
  69.                         foreach (Token token in m_Tokens)
  70.                         {
  71.                                 // Get the token value
  72.                                 string tokenValue = token.Value;
  73.  
  74.                                 // Make it SQL safe
  75.                                 tokenValue = tokenValue.Replace("'", "''");
  76.  
  77.                                 // Wrap the token value in quotes, if it's not in quotes already (ie. might be a phrase search)
  78.                                 if (token.TokenType == TokenType.UserItem && !tokenValue.StartsWith("\"") && !tokenValue.EndsWith("\""))
  79.                                         tokenValue = string.Format("\"{0}\"", tokenValue);
  80.  
  81.                                 Debug.WriteLine(" - " + tokenValue);
  82.  
  83.                                 // Append the token value to the list
  84.                                 sb.Append(tokenValue);
  85.                                 sb.Append(" ");
  86.                         }
  87.  
  88.                         return sb.ToString().Trim();
  89.                 }
  90.  
  91.                 /// <summary>
  92.                 /// Parses the query and initialises the tokens.
  93.                 /// </summary>
  94.                 /// <param name="userQuery">The user query</param>
  95.                 /// <returns>[True] if query is valid, otherwise [False]</returns>
  96.                 public bool ParseTokens(string userQuery)
  97.                 {
  98.                         // First make sure that we've got an even number of quotes
  99.                         if (CountQuotes(userQuery) % 2 != 0)
  100.                         {
  101.                                 m_Error = "Invalid number of quote marks";
  102.                                 return false;
  103.                         }
  104.  
  105.                         // Clean up query
  106.                         userQuery = userQuery.ToLower();
  107.  
  108.                         // Query cannot start with a not operator, so remove it if applicable
  109.                         if (userQuery.StartsWith("-"))
  110.                                 userQuery.Substring(1);
  111.  
  112.                         // Parse the query into tokens
  113.                         const string pattern = @"(/\s*([A-Za-z0-9'(-^"")_\u00C0-\u00FF]+\*)|([A-Za-z0-9'(-^"")_\u00C0-\u00FF]+(\*{0,1}))|(-{0,1}[""][^""]*[""])|([\(\)])\s*/)";
  114.                         Regex re = new Regex(pattern, RegexOptions.IgnoreCase | RegexOptions.Compiled);
  115.                         MatchCollection matches = re.Matches(userQuery);
  116.  
  117.                         // Nothing parsed yet so no token
  118.                         m_Tokens.Clear();
  119.                         Token lastParsedToken = null;
  120.  
  121.                         // Parse the regex matches into a list of words
  122.                         // which we'll then turn into a list of tokens.
  123.                         List<string> words = ParseMatchesIntoWordList(matches);
  124.  
  125.                         // Iterate through all the matches in the query
  126.                         foreach (string word in words)
  127.                         {
  128.                                 // Get the token from the word
  129.                                 Token token = GetToken(word);
  130.  
  131.                                 if (lastParsedToken != null && (lastParsedToken.TokenType == TokenType.NoiseWord) && (token.TokenType & TokenType.BinaryOperator) == token.TokenType)
  132.                                 {
  133.                                         // Skip this token since it joins a noise word
  134.                                 }
  135.                                 else if (lastParsedToken == null && (token.TokenType & TokenType.Operator) == token.TokenType)
  136.                                 {
  137.                                         // Skip this as query cannot start with an operator
  138.                                 }
  139.                                 else if (token.TokenType == TokenType.NoiseWord)
  140.                                 {
  141.                                         UnrollExpression(TokenType.Operator);
  142.                                         lastParsedToken = token;
  143.                                 }
  144.                                 else
  145.                                 {
  146.                                         // Get the last (previous) token
  147.                                         Token lastToken = GetLastToken();
  148.  
  149.                                         if (token.TokenType == TokenType.UserItem)
  150.                                         {
  151.                                                 // Check if there is a previous token and if it is an expression, then add an 'AND' operator
  152.                                                 if (lastToken != null && (lastToken.TokenType & TokenType.Expression) == lastToken.TokenType)
  153.                                                 {
  154.                                                         m_Tokens.Add(m_BuiltInTokens["and"]);
  155.                                                 }
  156.                                         }
  157.                                         else if (((token.TokenType & TokenType.NotOperator) == token.TokenType) && lastToken != null && (lastToken.TokenType & TokenType.Expression) == lastToken.TokenType)
  158.                                         {
  159.                                                 // Same goes for not.  If this token is a 'NOT' operator and the last token is an
  160.                                                 // expression, then add an 'and' token to keep the syntax correct.
  161.                                                 m_Tokens.Add(m_BuiltInTokens["and"]);
  162.                                         }
  163.  
  164.                                         // Add the token to the list
  165.                                         m_Tokens.Add(token);
  166.  
  167.                                         // Update the last parsed token to this one
  168.                                         lastParsedToken = token;
  169.                                 }
  170.                         }
  171.  
  172.                         return IsValid();
  173.                 }
  174.  
  175.                 #region Private Helper Stuff
  176.  
  177.                 /// <summary>
  178.                 /// Validates the tokens and checks if they correctly form a query
  179.                 /// </summary>
  180.                 private bool IsValid()
  181.                 {
  182.                         if (m_Tokens.Count == 0)
  183.                         {
  184.                                 m_Error = "Search string is empty";
  185.                                 return false;
  186.                         }
  187.  
  188.                         bool valid = true;
  189.                         bool lastItemOK = false;
  190.                         TokenType nextItem = TokenType.UserItem | TokenType.LeftParenthis | TokenType.NotOperator;
  191.                         int balance = 0;
  192.  
  193.                         for (int tokIndex = 0; tokIndex < m_Tokens.Count; tokIndex++)
  194.                         {
  195.                                 Token token = m_Tokens[tokIndex];
  196.  
  197.                                 if ((token.TokenType & nextItem) != 0)
  198.                                 {
  199.                                         switch (token.TokenType)
  200.                                         {
  201.                                                 case (TokenType.UserItem):
  202.                                                         nextItem = TokenType.BinaryOperator | TokenType.RightParenthis;
  203.                                                         lastItemOK = true;
  204.                                                         break;
  205.  
  206.                                                 case (TokenType.AndOperator):
  207.                                                         nextItem = TokenType.UserItem | TokenType.NotOperator | TokenType.LeftParenthis;
  208.                                                         lastItemOK = false;
  209.                                                         break;
  210.  
  211.                                                 case (TokenType.NearOperator):
  212.                                                         nextItem = TokenType.UserItem;
  213.                                                         lastItemOK = false;
  214.                                                         break;
  215.  
  216.                                                 case (TokenType.OrOperator):
  217.                                                         nextItem = TokenType.UserItem | TokenType.LeftParenthis;
  218.                                                         lastItemOK = false;
  219.                                                         break;
  220.  
  221.                                                 case (TokenType.NotOperator):
  222.                                                         nextItem = TokenType.UserItem | TokenType.LeftParenthis;
  223.                                                         lastItemOK = false;
  224.                                                         break;
  225.  
  226.                                                 case (TokenType.LeftParenthis):
  227.                                                         balance++;
  228.                                                         nextItem = TokenType.UserItem;
  229.                                                         lastItemOK = false;
  230.                                                         break;
  231.  
  232.                                                 case (TokenType.RightParenthis):
  233.                                                         balance--;
  234.                                                         nextItem = TokenType.OrOperator | TokenType.AndOperator;
  235.                                                         lastItemOK = (balance <= 0);
  236.                                                         break;
  237.                                         }
  238.                                         if (balance < 0)
  239.                                         {
  240.                                                 valid = false;
  241.                                                 m_Error = "Mismatched parenthesis";
  242.                                                 break;
  243.                                         }
  244.                                 }
  245.                                 else
  246.                                 {
  247.                                         valid = false;
  248.                                         m_Error = "Unexpected word or character found: " + m_Tokens[tokIndex].Value;
  249.                                         break;
  250.                                 }
  251.                         }
  252.  
  253.                         if (balance != 0)
  254.                         {
  255.                                 valid = false;
  256.                                 m_Error = "Mismatched parenthesis";
  257.                         }
  258.                         else if (valid && !lastItemOK)
  259.                         {
  260.                                 valid = false;
  261.                                 m_Error = "Unexpected end of search string after: " + m_Tokens[m_Tokens.Count - 1].Value;
  262.                         }
  263.  
  264.                         return valid;
  265.                 }
  266.  
  267.                 [Flags]
  268.                 private enum TokenType
  269.                 {
  270.                         UserItem = 1,
  271.                         AndOperator = 2,
  272.                         OrOperator = 4,
  273.                         NotOperator = 8,
  274.                         LeftParenthis = 16,
  275.                         RightParenthis = 32,
  276.                         NearOperator = 64,
  277.                         NoiseWord = 128,
  278.  
  279.                         Operator = AndOperator | OrOperator | NotOperator | NearOperator,
  280.                         BinaryOperator = AndOperator | OrOperator | NearOperator,
  281.                         Expression = RightParenthis | UserItem
  282.                 }
  283.  
  284.                 /// <summary>
  285.                 /// Gets a token from the specified text
  286.                 /// </summary>
  287.                 private static Token GetToken(string text)
  288.                 {
  289.                         if (m_BuiltInTokens.ContainsKey(text))
  290.                                 return m_BuiltInTokens[text];
  291.  
  292.                         Token token = new Token();
  293.                         token.Value = text;
  294.                         token.TokenType = m_NoiseWords.Contains(text) ? TokenType.NoiseWord : TokenType.UserItem;
  295.  
  296.                         return token;
  297.                 }
  298.  
  299.                 /// <summary>
  300.                 /// Gets the last token in the list.  If there is no last token, null is returned
  301.                 /// </summary>
  302.                 private Token GetLastToken()
  303.                 {
  304.                         if (m_Tokens.Count > 0)
  305.                                 return m_Tokens[m_Tokens.Count - 1];
  306.  
  307.                         return null;
  308.                 }
  309.  
  310.                 /// <summary>
  311.                 /// Rolls back to the last token of the specified type.
  312.                 /// All tokens after it are removed from the list.
  313.                 /// </summary>
  314.                 private void UnrollExpression(TokenType type)
  315.                 {
  316.                         for (int i = m_Tokens.Count; i > 0; i--)
  317.                         {
  318.                                 Token tok = m_Tokens[i - 1];
  319.  
  320.                                 if ((tok.TokenType & type) != 0)
  321.                                 {
  322.                                         m_Tokens.Remove(tok);
  323.                                 }
  324.                                 else
  325.                                 {
  326.                                         break;
  327.                                 }
  328.                         }
  329.                 }
  330.  
  331.                 /// <summary>
  332.                 /// Counts how many times the quote (") character appears in the specified string
  333.                 /// </summary>
  334.                 private static int CountQuotes(IEnumerable<char> s)
  335.                 {
  336.                         int count = 0;
  337.  
  338.                         foreach (char c in s)
  339.                         {
  340.                                 if (c == '"')
  341.                                         count++;
  342.                         }
  343.  
  344.                         return count;
  345.                 }
  346.  
  347.                 /// <summary>
  348.                 /// Parses the match collection into a list of words or phrases that need to be tokenized
  349.                 /// </summary>
  350.                 private static List<string> ParseMatchesIntoWordList(MatchCollection matches)
  351.                 {
  352.                         // This will contain our list of raw words
  353.                         List<String> wordList1 = new List<string>();
  354.  
  355.                         // The current word we've got.  We store this to check if it's a valid
  356.                         // word before we add it.  This is because the regex doesn't parse
  357.                         // all types of phrases correctly, so we need to build up the phrase
  358.                         // before it can be added to the list.
  359.  
  360.                         // For example, "bunch of grapes" will be parsed by the regex as: "bunch, of, grapes"
  361.                         // The problem with this is that it then breaks the SQL clause generator.
  362.                         // Instead, we hack around this by converting this back into a single phrase as we
  363.                         // build up the word list.
  364.  
  365.                         string currentWord = string.Empty;
  366.  
  367.                         foreach (Match match in matches)
  368.                         {
  369.                                 if (currentWord == string.Empty)
  370.                                 {
  371.                                         // This is a new word, so set our current word
  372.                                         currentWord = match.Value;
  373.  
  374.                                         // If the word starts with a quote or -quote, and doesn't end with one then
  375.                                         // skip to the next word.  We need to do this until we find the word with
  376.                                         // the end quote, and add the whole word as single word to our word list.
  377.                                         // This is because the regex has trouble parsing all permutations of phrases
  378.                                         // so we're hacking around some of the problems by using this method.
  379.  
  380.                                         if ((currentWord.StartsWith("-\"") || currentWord.StartsWith("\"")) && !currentWord.EndsWith("\""))
  381.                                         {
  382.                                                 continue;
  383.                                         }
  384.                                 }
  385.                                 else
  386.                                 {
  387.                                         // Otherwise, we've got a word already which begins with a quote.
  388.                                         // First we need to append it to our list.  Then we check if it doesn't
  389.                                         // end with a quote, and if so, move to the next word.  This is so we can
  390.                                         // build up the phrase that are properly delimited.
  391.  
  392.                                         currentWord += " " + match.Value;
  393.  
  394.                                         if (!currentWord.EndsWith("\""))
  395.                                         {
  396.                                                 continue;
  397.                                         }
  398.                                 }
  399.  
  400.                                 // All done.  Add our word or phrase to the list.
  401.                                 wordList1.Add(currentWord);
  402.  
  403.                                 // Clear the word, so that we can work on the next one in the list.
  404.                                 currentWord = string.Empty;
  405.                         }
  406.  
  407.                         // Raw list of words
  408.                         List<String> wordList2 = new List<string>();
  409.  
  410.                         // Add each match to the word list
  411.                         foreach (string w in wordList1)
  412.                         {
  413.                                 // Get the word
  414.                                 string word = w;
  415.  
  416.                                 // For words (or phrases) starting with a hypen
  417.                                 // remove it and insert 'not' before it in the tokenlist
  418.                                 if (word.StartsWith("-"))
  419.                                 {
  420.                                         word = word.Substring(1);
  421.                                         wordList2.Add("not");
  422.                                 }
  423.  
  424.                                 wordList2.Add(word);
  425.                         }
  426.  
  427.                         return wordList2;
  428.                 }
  429.  
  430.                 private class Token
  431.                 {
  432.                         public TokenType TokenType;
  433.                         public string Value;
  434.  
  435.                         public Token()
  436.                         {
  437.                         }
  438.  
  439.                         public Token(TokenType tokenType, string value)
  440.                         {
  441.                                 TokenType = tokenType;
  442.                                 Value = value;
  443.                         }
  444.  
  445.                         public override string ToString()
  446.                         {
  447.                                 return Value;
  448.                         }
  449.                 }
  450.  
  451.                 #endregion
  452.         }
  453. }