{"id":170457,"date":"2010-03-27T22:59:19","date_gmt":"2010-03-27T22:59:19","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/project\/rex-regular-expression-exploration\/"},"modified":"2017-06-14T14:56:35","modified_gmt":"2017-06-14T21:56:35","slug":"rex-regular-expression-exploration","status":"publish","type":"msr-project","link":"https:\/\/www.microsoft.com\/en-us\/research\/project\/rex-regular-expression-exploration\/","title":{"rendered":"Rex &#8211; Regular Expression Exploration"},"content":{"rendered":"<p class=\"asset-content\">Rex is a tool that explores .NET regexes and generates members efficiently.<!-- .asset-content --><\/p>\n<h1>Try out\u00a0Rex in duel mode at <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/rise4fun.com\/rex\">http:\/\/rise4fun.com\/rex<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>!<\/h1>\n<p><b>The duel mode is a game\u00a0where you have\u00a0to <\/b><b><em>guess a secret (hidden) regex<\/em><\/b><b>.<\/b> On each attempt, Rex generates strings that match or don&#8217;t match the same way as the secret regex. The game uses the ASCII range of characters, i.e. characters from code 0 to 127 and displays various automata associated to\u00a0the regexes.<\/p>\n<h2><span id=\"896faea0-7da2-48f8-9e87-22b5f718b0e4\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image896faea0-7da2-48f8-9e87-22b5f718b0e4\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-rexduel.png\" alt=\"\" \/><\/span><\/h2>\n<h2>How does the duel work?<\/h2>\n<p>There is a <strong><em>secret regex<\/em><\/strong> <em>S<\/em> and a <em><strong>given regex<\/strong><\/em> <em>R<\/em>. When you <strong>ask rex<\/strong>, a table is displayed showing (up to two) members of<\/p>\n<ul>\n<li>L(<em>R<\/em>) <em>intersect<\/em> L(<em>S<\/em>),<\/li>\n<li>L(<em>R<\/em>) <em>minus<\/em> L(<em>S<\/em>),<\/li>\n<li>L(<em>S<\/em>) <em>minus<\/em> L(<em>R<\/em>), and<\/li>\n<li>complement(L(<em>R<\/em>) <em>union<\/em> L(<em>S<\/em>)),<\/li>\n<\/ul>\n<p>where L(<em>r<\/em>) denotes the set of all strings\u00a0matching a regex <em>r. <\/em>In addition, the following automata are shown for <em>R<\/em>:<\/p>\n<ul>\n<li><strong>(e)NFA<\/strong>: <strong>N<\/strong>ondeterministic <strong>F<\/strong>inite <strong>A<\/strong>utomaton (with <strong>e<\/strong>psilon moves),<\/li>\n<li><strong>(min)DFA<\/strong>: (<strong>min<\/strong>imal) <strong>D<\/strong>eterministic <strong>F<\/strong>inite <strong>A<\/strong>utomaton<\/li>\n<\/ul>\n<p>All automata are displayed in <em>symbolic<\/em> or <em>extended<\/em> form, meaning that the labels on the transitions denote (nonempty)\u00a0<em>sets of characters<\/em> rather than individual characters.<\/p>\n<p>The\u00a0duel\u00a0also displays an NFA accepting L(S) <em>minus<\/em> L(R), denoted by <strong>NFA(S-R)<\/strong>.<\/p>\n<p>Duels\u00a0uses features of the underlying automata library (used by Rex) such as:<\/p>\n<ul>\n<li>construction of symbolic finite automata (SFAs) from .<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx\">NET regexes<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<li>difference construction of SFAs<\/li>\n<li>equivalence checking of SFAs<\/li>\n<li>intersection of SFAs<\/li>\n<li>complemetation of SFAs<\/li>\n<li>minimization of SFAs<\/li>\n<li>visualization of SFAs as directed graphs using <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/project\/microsoft-automatic-graph-layout\/\">MSAGL<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<\/ul>\n\t\t\t<div class=\"moray-accordion\" data-show=\"false\">\n\t\t\t\t\t\t\t<div class=\"clearfix\">\n\t\t\t\t\t<div\n\t\t\t\t\t\tclass=\"btn-group align-items-center mb-g float-sm-right\"\n\t\t\t\t\t\trole=\"group\"\n\t\t\t\t\t\tdata-mount=\"collapse-controls\"\n\t\t\t\t\t\tdata-bi-aN=\"accordion-collapse-controls\"\n\t\t\t\t\t\tdata-target=\"#accordion-1\">\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"expand\" type=\"button\" data-bi-cN=\"Expand all\">Expand all<\/button>\n\t\t\t\t\t\t<span aria-hidden=\"true\"> | <\/span>\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"collapse\" type=\"button\" data-bi-cN=\"Collapse all\">Collapse all<\/button>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<ul class=\"accordion\" id=\"accordion-1\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-2\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-2\">\n\t\tCreate your own duels!\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-2\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<ol>\n<li>In <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.rise4fun.com\/rex\">http:\/\/www.rise4fun.com\/rex<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> write two regexes on separate lines, say <em>R<\/em> and <em>S<\/em><\/li>\n<li>Click <b>permalink<\/b> to create a duel where<b> <\/b><b><em>R<\/em><\/b><b> is visible<\/b> and <b><em>S<\/em><\/b><b> is hidden<\/b>.This creates a <em>permanent web link<\/em> containing the duel.<\/li>\n<\/ol>\n<p><b><em>You have created your own duel!<\/em><\/b><\/p>\n<h3>Example<\/h3>\n<p>Enter regexes <em>R<\/em> and <em>S <\/em>(note that <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx#miscellaneous_constructs\" target=\"_self\">comments <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>can be added to regexes) and click <em>permalink<\/em>:<\/p>\n<p><span id=\"b4797641-a8f3-4356-93ad-f8e1ce121201\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Imageb4797641-a8f3-4356-93ad-f8e1ce121201\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-enterrexduelregexes.gif\" alt=\"\" \/><span id=\"ImageCaptionb4797641-a8f3-4356-93ad-f8e1ce121201\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n<p>This particular example is the link <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.rise4fun.com\/Rex\/abG\">http:\/\/www.rise4fun.com\/Rex\/abG<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.When you visit the link, <em>only R is shown<\/em>, <em>S remains secret<\/em>:<span id=\"becf5cc3-0f8d-4ed7-836d-7ff9970116f2\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Imagebecf5cc3-0f8d-4ed7-836d-7ff9970116f2\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-createrexduelpermalink.gif\" alt=\"\" \/><span id=\"ImageCaptionbecf5cc3-0f8d-4ed7-836d-7ff9970116f2\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span>When you now\u00a0<strong>ask rex<\/strong>, the following results are shown:<span id=\"94c94bc8-0591-469e-8f34-ef5dc2a6dc15\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Image94c94bc8-0591-469e-8f34-ef5dc2a6dc15\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-visitrexduelsamplelink.gif\" alt=\"\" \/><span id=\"ImageCaption94c94bc8-0591-469e-8f34-ef5dc2a6dc15\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n<h2>About .NET regex constructs<\/h2>\n<p>Most regex constructs are explained in .<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx\">NET regexes<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.<\/p>\n<h3>Using character classes<\/h3>\n<p>Regarding character classes, a less known but useful construct is <b><em>subtraction<\/em><\/b> operation in <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx#character_classes\">character classes<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>:<\/p>\n<ul>\n<li>[character_class-[character_class]]<\/li>\n<\/ul>\n<h3>Using comments<\/h3>\n<p>When writing regexes, you can insert <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx#miscellaneous_constructs\" target=\"_self\">comments<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, e.g., to provide a hint in the given regex in the duel, for solving the secret regex<\/p>\n<ul>\n<li>(?# comment text)<\/li>\n<\/ul>\n<h3>Examples:<\/h3>\n<ul>\n<li>[a-z-[d-g]](?# the set of all lowercase letters except d, e,\u00a0f and g)<em>note the two different meanings of -, used in this character class<\/em><\/li>\n<li>[w-[d]](?# the set of all word characters except digits)<em>e.g., [w-[d]] is equivalent (in ASCII range) to [a-zA-Z_] or [w-[0-9]]<\/em><\/li>\n<li>[a-[a]](?# the <em>empty<\/em> set of characters)<\/li>\n<li>^[a-z]+$(?# regex matching one or more lowercase letters)<\/li>\n<li>^d{2,}$(?# regex matching two or more decimal digits)<em>e.g., ^d{2,}$ is equivalent to ^[0-9]{2,}$ or ^dd+$<\/em><\/li>\n<\/ul>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-3\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-3\">\n\t\tWhat does Rex do?\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-3\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<p>Rex is a simple command line tool that takes a <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/az24scfc.aspx\" target=\"_self\">.NET regex pattern <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>or several regex patterns\u00a0and generates matching\u00a0string(s) for them. Rex can also be used through an API. Rex is fast, using a novel approach to solve this problem. When several regexes are provided, rex can be used to generate members that match <em>all<\/em> the regexes. By default, rex assumes UTF16 encoding of characters, but can also be restricted to ASCII ecoding.<\/p>\n<p>The following example generates 10 strings that start and end with a digit and have at least two characters:<\/p>\n<pre>> rex.exe \"^d.*d$\" \/k:10<\/pre>\n<p>In order to produce members that contain only ascii characters the \/e option can be used. For general instructions\u00a0regarding usage run:<\/p>\n<pre>> rex.exe \/?<\/pre>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-4\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-4\">\n\t\tHow does Rex work?\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-4\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<p>1) A regex pattern (or several patterns) is translated into a <em>symbolic finite automaton<\/em><\/p>\n<p>^[0-9]+|[a-z]$\u00a0\u00a0 ==>\u00a0 <span id=\"a53fb639-3fbd-4967-8c55-9df5670f106a\" class=\"ImageBlock fn\"><img decoding=\"async\" id=\"Imagea53fb639-3fbd-4967-8c55-9df5670f106a\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-samplesfa.jpg\" alt=\"\" \/><span id=\"ImageCaptiona53fb639-3fbd-4967-8c55-9df5670f106a\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n<p>2) The automaton is given to a constraint solver that generates members from it.<\/p>\n<h2>Watch the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/channel9.msdn.com\/posts\/Peli\/Margus-Veanes-Rex-Symbolic-Regular-Expression-Exploration\/\" target=\"_self\">Channel9 Movie!<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><span id=\"ae66c128-9f10-4230-bd19-b5bd1a0f7cdb\" class=\"ImageBlock fn\"><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/channel9.msdn.com\/posts\/Peli\/Margus-Veanes-Rex-Symbolic-Regular-Expression-Exploration\/\" target=\"_self\"><img decoding=\"async\" id=\"Imageae66c128-9f10-4230-bd19-b5bd1a0f7cdb\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-rexvideo.png\" alt=\"\" \/><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/span><\/h2>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t\t\t\t<\/ul>\n\t\t<\/div>\n\t\t\n<p>Try out <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.pexforfun.com\/Default.aspx?language=CSharp&sample=RegularExpressions\" target=\"_new\">Pex on the web<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>!<span id=\"bb2e56d2-3e31-4f41-9af6-93bf134f3ca7\" class=\"ImageBlock fn\"><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.pexforfun.com\/Default.aspx?language=CSharp&sample=RegularExpressions\" target=\"_new\"><img decoding=\"async\" id=\"Imagebb2e56d2-3e31-4f41-9af6-93bf134f3ca7\" title=\"Rex for fun\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/rex-pexforfunverysmall.png\" alt=\"Rex for fun\" \/><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><span id=\"ImageCaptionbb2e56d2-3e31-4f41-9af6-93bf134f3ca7\" class=\"ImageCaptionCoreCss ImageCaption\"><\/span><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Rex is a tool that explores .NET regexes and generates members efficiently. Try out\u00a0Rex in duel mode at http:\/\/rise4fun.com\/rex! The duel mode is a game\u00a0where you have\u00a0to guess a secret (hidden) regex. On each attempt, Rex generates strings that match or don&#8217;t match the same way as the secret regex. The game uses the ASCII [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13560],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-170457","msr-project","type-msr-project","status-publish","hentry","msr-research-area-programming-languages-software-engineering","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2010-03-27","related-publications":[158730,158942,159863,165174,165785],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[{"type":"user_nicename","value":"jhalleux","display_name":"Peli de Halleux","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/jhalleux\/\" aria-label=\"Visit the profile page for Peli de Halleux\">Peli de Halleux<\/a>","is_active":false,"user_id":32253,"last_first":"de Halleux, Peli","people_section":0,"alias":"jhalleux"},{"type":"user_nicename","value":"margus","display_name":"Margus Veanes","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/margus\/\" aria-label=\"Visit the profile page for Margus Veanes\">Margus Veanes<\/a>","is_active":false,"user_id":32806,"last_first":"Veanes, Margus","people_section":0,"alias":"margus"}],"msr_research_lab":[199565],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170457"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170457\/revisions"}],"predecessor-version":[{"id":390560,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170457\/revisions\/390560"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=170457"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=170457"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=170457"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=170457"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=170457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}