นิพจน์ทั่วไป

วลีที่แสดงออกปกติหรือregexesมักใช้ในความหมายที่เฉพาะเจาะจงเกี่ยวกับใจไวยากรณ์มาตรฐานสำหรับการเป็นตัวแทนของรูปแบบสำหรับข้อความที่ตรงกันแตกต่างไปจากสัญกรณ์คณิตศาสตร์อธิบายไว้ด้านล่าง อักขระแต่ละตัวในนิพจน์ทั่วไป (นั่นคืออักขระแต่ละตัวในสตริงที่อธิบายรูปแบบของมัน) อาจเป็นอักขระเมตาที่มีความหมายพิเศษหรืออักขระทั่วไปที่มีความหมายตามตัวอักษร ตัวอย่างเช่นใน regex b."b" คืออักขระตามตัวอักษรที่ตรงกับ "b" ในขณะที่ " เป็นอักขระเมตาที่ตรงกับอักขระทุกตัวยกเว้นขึ้นบรรทัดใหม่ ดังนั้น regex นี้จึงจับคู่เช่น "b%" หรือ "bx" หรือ "b5" สามารถใช้อักขระเมตาและอักขระตามตัวอักษรร่วมกันเพื่อระบุข้อความของรูปแบบที่กำหนดหรือประมวลผลอินสแตนซ์จำนวนมากได้ การจับคู่รูปแบบอาจแตกต่างกันไปตั้งแต่ความเท่าเทียมกันอย่างแม่นยำไปจนถึงความคล้ายคลึงกันโดยทั่วไปตามที่ควบคุมโดยอักขระเมตา ตัวอย่างเช่น.เป็นรูปแบบทั่วไปมาก[a-z](จับคู่ตัวอักษรตัวพิมพ์เล็กทั้งหมดจาก 'a' ถึง 'z') มีความกว้างน้อยกว่าและbเป็นรูปแบบที่แม่นยำ (จับคู่แค่ 'b') ไวยากรณ์ metacharacter ถูกออกแบบมาเพื่อเป็นตัวแทนของเป้าหมายที่กำหนดไว้ในที่กระชับและวิธีการที่ยืดหยุ่นเพื่อนำระบบอัตโนมัติของการประมวลผลข้อความของความหลากหลายของการป้อนข้อมูลในรูปแบบง่ายต่อการพิมพ์โดยใช้มาตรฐานASCII แป้นพิมพ์

กรณีที่ง่ายมากของนิพจน์ทั่วไปในไวยากรณ์นี้คือการค้นหาคำที่สะกดสองวิธีที่แตกต่างกันในโปรแกรมแก้ไขข้อความโดยนิพจน์ทั่วไปจะseriali[sz]eจับคู่ทั้ง "serialise" และ "serialize" อักขระไวลด์การ์ดก็ทำได้เช่นกัน แต่มีข้อ จำกัด มากกว่าในรูปแบบที่สามารถทำได้เนื่องจากมีอักขระเมตาคาร์ดน้อยลงและมีพื้นฐานภาษาที่เรียบง่าย

บริบทปกติของอักขระตัวแทนอยู่ในglobbingชื่อที่คล้ายกันในรายชื่อของไฟล์ในขณะที่ regexes มักจะมีการจ้างงานในการใช้งานที่สตริงข้อความรูปแบบการแข่งขันในทั่วไป ตัวอย่างเช่น regex จะจับคู่ช่องว่างส่วนเกินที่จุดเริ่มต้นหรือจุดสิ้นสุดของบรรทัด การแสดงออกปกติขั้นสูงที่ตรงกับเลขใด ๆ ที่เป็น^[ \t]+|[ \t]+$[+-]?(\d+(\.\d+)?|\.\d+)([eE][+-]?\d+)?

แปลKleene ดาว
( sวิธี * "ศูนย์หรือมากกว่าของ s ")

ประมวลผล regexแปลนิพจน์ปกติในไวยากรณ์ข้างต้นเป็นตัวแทนภายในที่สามารถดำเนินการและจับคู่กับสตริงตัวแทนเป็นข้อความค้นหาใน. วิธีการหนึ่งที่เป็นไปได้คือขั้นตอนวิธีการก่อสร้าง ธ อมป์สันที่จะสร้างหุ่นยนต์ จำกัด nondeterministic (NFA) ซึ่ง จากนั้นจะถูกกำหนดให้เป็นแบบดีเทอร์มินิสติกและผลลัพธ์ที่ได้จากการกำหนดอัตโนมัติ จำกัด (DFA) จะถูกรันบนสตริงข้อความเป้าหมายเพื่อรับรู้สตริงย่อยที่ตรงกับนิพจน์ทั่วไป ภาพแสดงโครงร่าง NFA ที่ได้รับจากนิพจน์ทั่วไปโดยที่sหมายถึงนิพจน์ทั่วไปที่ง่ายกว่าซึ่งได้รับการแปลซ้ำเป็น NFA N ( s ) แล้วN(s*)s*

การแสดงออกปกติเกิดขึ้นในปี 1951 เมื่อนักคณิตศาสตร์สตีเฟนโคลคลีนอธิบายภาษาปกติโดยใช้สัญกรณ์คณิตศาสตร์ของเขาที่เรียกว่าเหตุการณ์ที่เกิดขึ้นเป็นประจำ ^{[4] [5]}เหล่านี้เกิดขึ้นในวิชาวิทยาการคอมพิวเตอร์ในฟิลด์ของทฤษฎีออโต (รูปแบบของการคำนวณ) และรายละเอียดและการจำแนกประเภทของภาษาอย่างเป็นทางการ การนำไปใช้ในช่วงต้นอื่น ๆ ของการจับคู่รูปแบบได้แก่ภาษาSNOBOLซึ่งไม่ได้ใช้นิพจน์ทั่วไป แต่ใช้โครงสร้างการจับคู่รูปแบบของตัวเองแทน

นิพจน์ทั่วไปเข้าสู่การใช้ที่นิยมตั้งแต่ปี 1968 โดยใช้สองแบบ: การจับคู่รูปแบบในโปรแกรมแก้ไขข้อความ^[6]และการวิเคราะห์ศัพท์ในคอมไพเลอร์ ^[7]ท่ามกลางการปรากฏตัวครั้งแรกของการแสดงผลปกติในรูปแบบโปรแกรมได้เมื่อเคน ธ อมป์สันสร้างสัญกรณ์ Kleene เข้าไปแก้ไขQEDเป็นวิธีที่จะตรงกับรูปแบบในไฟล์ข้อความ ^{[6] [8] [9] [10]}เพื่อความรวดเร็ว Thompson ได้ใช้การจับคู่นิพจน์ทั่วไปโดยการคอมไพล์แบบทันเวลา (JIT) กับโค้ดIBM 7094บนCompatible Time-Sharing Systemซึ่งเป็นตัวอย่างแรกเริ่มที่สำคัญของการคอมไพล์ JIT ^[11]ต่อมาเขาได้เพิ่มความสามารถนี้ให้กับ Unix editor edซึ่งในที่สุดก็นำไปสู่การใช้นิพจน์ทั่วไปของเครื่องมือค้นหาgrep ("grep" เป็นคำที่มาจากคำสั่งสำหรับการค้นหานิพจน์ทั่วไปในเอดิเตอร์ ed: ความหมาย "ค้นหาส่วนกลางสำหรับนิพจน์ทั่วไปและพิมพ์บรรทัดที่ตรงกัน") ^[12]ในช่วงเวลาเดียวกันกับที่ทอมป์สันพัฒนา QED กลุ่มนักวิจัยรวมถึงดักลาสทีรอสส์ได้ใช้เครื่องมือตามนิพจน์ทั่วไปที่ใช้สำหรับการวิเคราะห์ศัพท์ในการออกแบบคอมไพเลอร์ ^[7]g/re/p

หลายรูปแบบรูปแบบเดิมเหล่านี้แสดงออกปกติถูกนำมาใช้ในระบบปฏิบัติการยูนิกซ์^[10]โปรแกรมที่เบลล์แล็บในปี 1970 รวมทั้งvi , lex , sed , AWKและexprและในโปรแกรมอื่น ๆ เช่นEmacs ต่อมา Regexes ถูกนำมาใช้โดยโปรแกรมต่างๆมากมายโดยรูปแบบแรกเริ่มเหล่านี้ได้รับการกำหนดมาตรฐานในมาตรฐานPOSIX.2ในปี 1992

ในช่วงปี 1980 ที่ regexes ซับซ้อนมากขึ้นเกิดขึ้นในPerlซึ่ง แต่เดิมมาจากห้องสมุด regex เขียนโดยเฮนรี่สเปนเซอร์ (1986) ซึ่งต่อมาเขียนการดำเนินการขั้นสูงนิพจน์ปกติสำหรับTcl ^[13]ไลบรารี Tcl เป็นการใช้งานNFA / DFAแบบไฮบริดที่มีคุณลักษณะด้านประสิทธิภาพที่ดีขึ้น โครงการซอฟแวร์ที่ได้นำ Tcl ดำเนินการแสดงออกปกติของสเปนเซอร์ ได้แก่PostgreSQL ^[14]ต่อมา Perl ได้ขยายในไลบรารีดั้งเดิมของ Spencer เพื่อเพิ่มคุณสมบัติใหม่ ๆ มากมาย ^[15]ส่วนหนึ่งของความพยายามในการออกแบบRaku (เดิมชื่อ Perl 6) คือการปรับปรุงการรวม regex ของ Perl และเพิ่มขอบเขตและความสามารถเพื่อให้สามารถกำหนดไวยากรณ์ของนิพจน์ที่แยกวิเคราะห์ได้ ^[16]ผลลัพธ์ที่ได้คือภาษาขนาดเล็กที่เรียกว่ากฎ Rakuซึ่งใช้ในการกำหนดไวยากรณ์ของ Raku รวมทั้งจัดหาเครื่องมือให้กับโปรแกรมเมอร์ในภาษานั้น ๆ กฎเหล่านี้ยังคงรักษาคุณลักษณะที่มีอยู่ของ regexes Perl 5.x แต่ยังอนุญาตให้ใช้นิยามสไตล์BNFของตัวแยกวิเคราะห์การสืบเชื้อสายซ้ำผ่านกฎย่อย

การใช้ regexes ในมาตรฐานข้อมูลที่มีโครงสร้างสำหรับการสร้างแบบจำลองเอกสารและฐานข้อมูลเริ่มต้นในทศวรรษที่ 1960 และขยายตัวในทศวรรษที่ 1980 เมื่อมาตรฐานอุตสาหกรรมเช่นISO SGML (ซึ่งถูกตั้งค่าโดย ANSI "GCA 101-1983") รวมเข้าด้วยกัน เคอร์เนลของมาตรฐานภาษาข้อกำหนดโครงสร้างประกอบด้วยนิพจน์ทั่วไป การใช้งานจะเห็นได้ชัดในไวยากรณ์กลุ่มองค์ประกอบDTD

เริ่มต้นในปี 1997 ฟิลิปเฮเซลพัฒนาPCRE (นิพจน์ปกติ Perl เข้ากันได้) ซึ่งพยายามที่จะเลียนแบบการทำงานอย่างใกล้ชิดของ Perl regex และถูกใช้โดยเครื่องมือที่ทันสมัยจำนวนมากรวมทั้งPHPและApache HTTP Server

ปัจจุบัน regexes ได้รับการสนับสนุนอย่างกว้างขวางในภาษาโปรแกรมโปรแกรมประมวลผลข้อความ (โดยเฉพาะlexers ) โปรแกรมแก้ไขข้อความขั้นสูงและโปรแกรมอื่น ๆ สนับสนุน Regex เป็นส่วนหนึ่งของห้องสมุดมาตรฐานของภาษาโปรแกรมจำนวนมากรวมทั้งJavaและงูหลามและถูกสร้างขึ้นในไวยากรณ์ของคนอื่น ๆ รวมทั้ง Perl และECMAScript การใช้งานฟังก์ชัน regex มักเรียกว่าregex engineและมีไลบรารีจำนวนหนึ่งสำหรับการใช้ซ้ำ ในช่วงปลายยุค 2010 หลาย บริษัท เริ่มที่จะฮาร์ดแวร์เสนอFPGA , ^[17] GPU ^[18]การใช้งานของPCREเข้ากันได้เครื่องมือ regexที่เร็วขึ้นเมื่อเทียบกับCPU การใช้งาน

นิพจน์ทั่วไปมักเรียกว่ารูปแบบระบุชุดของสตริงที่จำเป็นสำหรับวัตถุประสงค์เฉพาะ วิธีง่ายๆในการระบุชุดสตริงที่ จำกัด คือการแสดงรายการองค์ประกอบหรือสมาชิก แต่มีวิธีการที่มักจะกระชับมากขึ้น: ยกตัวอย่างเช่นชุดที่มีสามสาย "ฮันเดล", "Händel" และ "Haendel" สามารถระบุโดยรูปแบบH(ä|ae?)ndel; เราบอกว่ารูปแบบนี้ตรงกับสตริงทั้งสาม ในความเป็นทางการส่วนใหญ่หากมีนิพจน์ทั่วไปอย่างน้อยหนึ่งนิพจน์ที่ตรงกับชุดเฉพาะแสดงว่ามีนิพจน์ทั่วไปอื่น ๆ จำนวนไม่ จำกัด ที่จับคู่ด้วยเช่นกันข้อกำหนดจะไม่ซ้ำกัน พิธีการส่วนใหญ่จัดเตรียมการดำเนินการต่อไปนี้เพื่อสร้างนิพจน์ทั่วไป

บูลีน "หรือ"

แถบแนวตั้งทางเลือกแยก ตัวอย่างเช่น สามารถจับคู่ "สีเทา" หรือ "สีเทา" gray|grey

การจัดกลุ่ม

วงเล็บใช้เพื่อกำหนดขอบเขตและลำดับความสำคัญของตัว ดำเนินการ (รวมถึงการใช้งานอื่น ๆ ) ตัวอย่างเช่น gray|greyและ เป็นรูปแบบที่เท่ากันซึ่งทั้งคู่อธิบายถึงชุดของ "สีเทา" หรือ "สีเทา" gr(a|e)y

ปริมาณ

ตัว ระบุปริมาณหลัง โทเค็น (เช่นอักขระ) หรือกลุ่มระบุความถี่ที่อนุญาตให้องค์ประกอบก่อนหน้าเกิดขึ้น ปริมาณที่พบมากที่สุดเป็น เครื่องหมายคำถาม?ที่ เครื่องหมายดอกจัน* (มาจาก Kleene ดาว ) และ เครื่องหมายบวก+ ( Kleene บวก )

?	เครื่องหมายคำถามแสดงถึงศูนย์หรือหนึ่งเหตุการณ์ที่เกิดขึ้นก่อนหน้านี้ ตัวอย่างเช่นcolou?rจับคู่ทั้ง "color" และ "color"
*	เครื่องหมายดอกจันหมายถึงการเกิดขึ้นขององค์ประกอบก่อนหน้าเป็นศูนย์หรือมากกว่านั้น ตัวอย่างเช่นab*cจับคู่ "ac" "abc" "abbc" "abbbc" เป็นต้น
+	เครื่องหมายบวกบ่งชี้เหตุการณ์ที่เกิดขึ้นอย่างน้อยหนึ่งครั้งขององค์ประกอบก่อนหน้า ตัวอย่างเช่นab+cจับคู่ "abc", "abbc", "abbbc" และอื่น ๆ แต่ไม่ใช่ "ac"
{n}[19]	รายการก่อนหน้านี้ตรงกันทุกประการnครั้ง
{min,}[19]	รายการก่อนหน้าตรงกับขั้นต่ำหรือมากกว่าครั้ง
{,max}[19]	รายการก่อนหน้านี้ตรงกับเวลาสูงสุด
{min,max}[19]	รายการก่อนหน้านี้ตรงกันอย่างน้อยครั้งต่ำสุดแต่ไม่เกินจำนวนครั้งสูงสุด

สัญลักษณ์แทน

สัญลักษณ์แทน.ตรงกับอักขระใด ๆ ตัวอย่างเช่นa.bจับคู่สตริงใด ๆ ที่มี "a" ตามด้วยอักขระอื่น ๆ และตามด้วย "b" a.*bจับคู่สตริงใด ๆ ที่มี "a" และตามด้วยอักขระ "b" ในภายหลัง

โครงสร้างเหล่านี้สามารถรวมกันเพื่อสร้างนิพจน์ที่ซับซ้อนตามอำเภอใจได้เช่นเดียวกับที่สามารถสร้างนิพจน์ทางคณิตศาสตร์จากตัวเลขและการดำเนินการ +, -, ×และ÷ ยกตัวอย่างเช่นH(ae?|ä)ndelและมีทั้งรูปแบบที่ถูกต้องซึ่งตรงกับสายเดียวกับตัวอย่างก่อนหน้านี้H(a|ae|ä)ndelH(ä|ae?)ndel

ไวยากรณ์ที่แม่นยำสำหรับนิพจน์ทั่วไปจะแตกต่างกันไปตามเครื่องมือและบริบท รายละเอียดเพิ่มเติมจะได้รับใน§ไวยากรณ์

นิพจน์ปกติอธิบายภาษาปกติในทฤษฎีภาษาอย่างเป็นทางการ พวกเขามีพลังในการแสดงออกเช่นเดียวกับไวยากรณ์ทั่วไป

คำจำกัดความที่เป็นทางการ

นิพจน์ทั่วไปประกอบด้วยค่าคงที่ซึ่งแสดงถึงชุดของสตริงและสัญลักษณ์ตัวดำเนินการซึ่งแสดงถึงการดำเนินการเหนือชุดเหล่านี้ คำจำกัดความต่อไปนี้เป็นมาตรฐานและพบได้ในหนังสือเรียนส่วนใหญ่เกี่ยวกับทฤษฎีภาษาที่เป็นทางการ ^{[20] [21]}ด้วยอักษรจำกัดΣค่าคงที่ต่อไปนี้ถูกกำหนดให้เป็นนิพจน์ทั่วไป:

• ( ชุดว่าง ) ∅แสดงถึงชุด∅
• ( สตริงว่าง ) εแสดงถึงชุดที่มีเฉพาะสตริง "ว่าง" ซึ่งไม่มีอักขระเลย
• ( ตัวอักษร ) aในΣแสดงถึงชุดที่มีเฉพาะอักขระa .

ด้วยนิพจน์ทั่วไป R และ S การดำเนินการต่อไปนี้จะถูกกำหนดเพื่อสร้างนิพจน์ทั่วไป:

• ( concatenation ) (RS)หมายถึงชุดของสตริงที่สามารถหาได้จากการต่อสตริงที่ยอมรับโดย R และสตริงที่ S ยอมรับ (ตามลำดับนั้น) ตัวอย่างเช่นให้ R แสดงว่า {"ab", "c"} และ S หมายถึง {"d", "ef"} จากนั้น(RS)หมายถึง {"abd", "abef", "cd", "cef"}
• ( alternation ) (R|S)หมายถึงการรวมเซตของเซตที่อธิบายโดย R และ S เช่นถ้า R อธิบายว่า {"ab", "c"} และ S อธิบายถึง {"ab", "d", "ef"} นิพจน์จะ(R|S)อธิบายถึง { "ab", "c", "d", "ef"}
• ( Kleene ดาว ) (R*)หมายถึงการที่เล็กที่สุดเซ็ตชุดอธิบายโดยRที่มีεและปิดภายใต้สตริง นี่คือชุดของสตริงทั้งหมดที่สามารถสร้างขึ้นโดยการเชื่อมต่อหมายเลข จำกัด ใด ๆ (รวมถึงศูนย์) ของสตริงจากชุดที่อธิบายโดย R ตัวอย่างเช่นถ้า R หมายถึง {"0", "1"} จะ(R*)หมายถึงชุดของทั้งหมดสตริงไบนารีจำกัด(รวมถึงสตริงว่าง) ถ้า R หมายถึง {"ab", "c"} (R*)แสดงว่า {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", .. }.

เพื่อหลีกเลี่ยงวงเล็บจะถือว่าดาวคลีนมีลำดับความสำคัญสูงสุดจากนั้นจึงเรียงต่อกันแล้วจึงสลับกัน หากไม่มีความคลุมเครือก็อาจละเว้นวงเล็บได้ ตัวอย่างเช่น(ab)cสามารถเขียนเป็นabcและa|(b(c*))สามารถเขียนเป็นa|bc*ไฟล์. หนังสือเรียนหลายเล่มใช้สัญลักษณ์∪, + หรือ∨สำหรับการสลับแทนแถบแนวตั้ง

ตัวอย่าง:

• a|b* หมายถึง {ε, "a", "b", "bb", "bbb", ... }
• (a|b)* หมายถึงชุดของสตริงทั้งหมดที่ไม่มีสัญลักษณ์อื่นใดนอกจาก "a" และ "b" รวมถึงสตริงว่าง: {ε, "a", "b", "aa", "ab", "ba", "bb" , "aaa", ... }
• ab*(c|ε) หมายถึงชุดของสตริงที่ขึ้นต้นด้วย "a" จากนั้นจึงเป็นศูนย์หรือมากกว่า "b" s และสุดท้ายคือเลือก "c": {"a", "ac", "ab", "abc", "abb", "abbc ", ... }
• (0|(1(01*0)*1))* หมายถึงชุดของเลขฐานสองที่ทวีคูณเป็น 3: {ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110" , "1001", "1100", "1111", "00000", ... }

พลังที่แสดงออกและความกะทัดรัด

ความหมายอย่างเป็นทางการของการแสดงออกปกติมีน้อยเกี่ยวกับวัตถุประสงค์และหลีกเลี่ยงการกำหนด?และ+-these สามารถแสดงเป็นดังนี้a+= aa*และ=a? (a|ε)บางครั้งสมบูรณ์ผู้ประกอบการจะมีการเพิ่มเพื่อให้การแสดงออกปกติทั่วไป ; นี่R ^คตรงกับสายทั่วΣ * ที่ไม่ตรงกับR โดยหลักการแล้วตัวดำเนินการส่วนเสริมนั้นซ้ำซ้อนเนื่องจากไม่ได้ให้อำนาจในการแสดงออกอีกต่อไป อย่างไรก็ตามมันสามารถทำให้นิพจน์ทั่วไปกระชับมากขึ้น - การกำจัดตัวดำเนินการส่วนเสริมเพียงตัวเดียวอาจทำให้ความยาวของมันเพิ่มขึ้นเป็นทวีคูณ ^{[22] [23] [24]}

การแสดงผลปกติในความรู้สึกนี้สามารถแสดงภาษาปกติว่าระดับของภาษาที่ยอมรับโดยออโต จำกัด กำหนด อย่างไรก็ตามมีความแตกต่างอย่างมีนัยสำคัญในความกะทัดรัด ภาษาทั่วไปบางคลาสสามารถอธิบายได้โดยออโตมาตา จำกัด ที่กำหนดซึ่งขนาดจะโตขึ้นแบบทวีคูณในขนาดของนิพจน์ทั่วไปที่สั้นที่สุดที่เทียบเท่ากัน ตัวอย่างมาตรฐานที่นี่เป็นภาษาL _kประกอบด้วยสายทั่วตัวอักษร { , ข } ซึ่งk ^THรินสุดท้ายจดหมายเท่ากับ ในแง่หนึ่งนิพจน์ทั่วไปที่อธิบายL ₄จะได้รับโดย${\ displaystyle (a \ mid b) ^ {*} a (a \ mid b) (a \ mid b) (a \ mid b)}$.

การสรุปรูปแบบนี้เป็นL _kให้นิพจน์:${\ displaystyle (a \ mid b) ^ {*} a \ underbrace {(a \ mid b) (a \ mid b) \ cdots (a \ mid b)} _ {k-1 {\ text {times}} }. \,}$

ในทางกลับกันก็เป็นที่รู้จักกันว่าทุกคนแน่นอนหุ่นยนต์กำหนดยอมรับภาษาL _kต้องมีอย่างน้อย 2 ^kรัฐ โชคดีที่มีการทำแผนที่อย่างง่ายจากนิพจน์ทั่วไปไปจนถึงออโตมาตา จำกัด แบบไม่กำหนดเฉพาะเจาะจง (NFAs) ทั่วไปที่ไม่ได้นำไปสู่การระเบิดขนาดนั้น ด้วยเหตุนี้จึงมักใช้ NFAs เป็นตัวแทนของภาษาปกติ NFAs มีรูปแบบที่เรียบง่ายของประเภท 3 ไวยากรณ์ของลำดับชั้นของชัม ^[20]

ในทางตรงกันข้ามมีหลายภาษาที่อธิบายได้ง่ายโดย DFA ซึ่งไม่ได้อธิบายง่ายๆว่าเป็นนิพจน์ทั่วไป ตัวอย่างเช่นการพิจารณาความถูกต้องของISBN ที่กำหนดต้องคำนวณโมดูลัสของฐานจำนวนเต็ม 11 และสามารถนำไปใช้กับ DFA 11 สถานะได้อย่างง่ายดาย อย่างไรก็ตามนิพจน์ทั่วไปเพื่อตอบปัญหาเดียวกันของการหารด้วย 11 มีความยาวอย่างน้อยหลายเมกะไบต์ ^{[ ต้องการอ้างอิง ]}

ด้วยนิพจน์ทั่วไปอัลกอริธึมการก่อสร้างของทอมป์สันจะคำนวณหุ่นยนต์ จำกัด ที่ไม่ได้กำหนดไว้เทียบเท่า แปลงไปในทิศทางตรงกันข้ามจะทำได้โดยอัลกอริทึมของ Kleene

สุดท้ายเป็นที่น่าสังเกตว่าเครื่องมือ "นิพจน์ทั่วไป" ในโลกแห่งความเป็นจริงจำนวนมากใช้คุณลักษณะที่ไม่สามารถอธิบายได้ด้วยนิพจน์ทั่วไปในความหมายของทฤษฎีภาษาที่เป็นทางการ แต่พวกเขาใช้regexes ดูด้านล่างสำหรับข้อมูลเพิ่มเติมเกี่ยวกับเรื่องนี้

การตัดสินใจความเท่าเทียมกันของนิพจน์ทั่วไป

ดังที่เห็นในหลาย ๆ ตัวอย่างข้างต้นมีมากกว่าหนึ่งวิธีในการสร้างนิพจน์ทั่วไปเพื่อให้ได้ผลลัพธ์ที่เหมือนกัน

เป็นไปได้ที่จะเขียนอัลกอริทึมที่สำหรับสองนิพจน์ทั่วไปที่กำหนดให้ตัดสินใจว่าภาษาที่อธิบายนั้นเท่าเทียมกันหรือไม่ อัลกอริทึมจะลดนิพจน์แต่ละรายการให้เป็นเครื่องกำหนดสถานะ จำกัด ที่น้อยที่สุดและพิจารณาว่าเป็นไอโซมอร์ฟิก (เทียบเท่า) หรือไม่

กฎพีชคณิตสำหรับนิพจน์ทั่วไปสามารถหาได้โดยใช้วิธีการของ Gischer ซึ่งอธิบายได้ดีที่สุดพร้อมตัวอย่าง: เพื่อตรวจสอบว่า ( X + Y ) ^*และ ( X ^* Y ^* ) ^*แสดงถึงภาษาปกติเดียวกันหรือไม่สำหรับนิพจน์ทั่วไปทั้งหมดX , Yจำเป็นและเพียงพอที่จะตรวจสอบว่านิพจน์ทั่วไป ( a + b ) ^*และ ( a ^* b ^* ) ^*แสดงภาษาเดียวกันทับตัวอักษรΣ = { a , b } หรือไม่ โดยทั่วไปแล้วสมการE = Fระหว่างเงื่อนไขนิพจน์ทั่วไปที่มีตัวแปรจะถือในกรณีที่และเฉพาะในกรณีที่การสร้างอินสแตนซ์ของตัวแปรที่แตกต่างกันถูกแทนที่ด้วยค่าคงที่สัญลักษณ์ที่ต่างกัน ^{[25] [26]}

ความซ้ำซ้อนสามารถกำจัดได้โดยใช้Kleene starและตั้งค่าการรวมกันเพื่อค้นหานิพจน์ทั่วไปที่น่าสนใจซึ่งยังคงแสดงออกได้อย่างสมบูรณ์ แต่อาจ จำกัด การใช้งานได้ ^{[ ต้องการคำชี้แจง ]}นี่เป็นปัญหาที่ยากอย่างน่าประหลาดใจ เรียบง่ายเหมือนนิพจน์ทั่วไปไม่มีวิธีใดในการเขียนซ้ำอย่างเป็นระบบให้เป็นรูปแบบปกติ การขาดความจริงในอดีตที่ผ่านมาจะนำไปสู่ปัญหาความสูงดาว ในปีพ. ศ. 2534 Dexter Kozen ได้นำนิพจน์ทั่วไปมาใช้เป็นพีชคณิตแบบคลีนโดยใช้สัจพจน์สมการและฮอร์น ^[27]ในปีพ. ศ. 2507 Redko ได้พิสูจน์แล้วว่าไม่มีชุดใดของสัจพจน์ที่เท่าเทียมกันอย่างแท้จริงที่สามารถอธิบายลักษณะของพีชคณิตของภาษาปกติได้ ^[28]

regex รูปแบบที่ตรงกับเป้าหมายสตริง รูปแบบประกอบด้วยลำดับของอะตอม อะตอมเป็นจุดเดียวภายในรูปแบบนิพจน์ทั่วไปที่พยายามจับคู่กับสตริงเป้าหมาย อะตอมที่ง่ายที่สุดคือตัวอักษร แต่การจัดกลุ่มส่วนต่างๆของรูปแบบเพื่อให้ตรงกับอะตอมจะต้องใช้( )เป็นอักขระเมตา Metacharacters ช่วยในรูปแบบ: อะตอม ; ตัวบอกปริมาณบอกจำนวนอะตอม (และเป็นตัวบอกปริมาณโลภหรือไม่) ตรรกะหรืออักขระซึ่งเสนอชุดของทางเลือกและอักขระ NOT เชิงตรรกะซึ่งลบล้างการมีอยู่ของอะตอม และการอ้างอิงย้อนกลับเพื่ออ้างถึงอะตอมก่อนหน้าของรูปแบบที่สมบูรณ์ของอะตอม การจับคู่จะเกิดขึ้นไม่ใช่เมื่ออะตอมทั้งหมดของสตริงถูกจับคู่ แต่เป็นเมื่อรูปแบบอะตอมทั้งหมดใน regex ตรงกัน แนวคิดคือการสร้างรูปแบบของอักขระขนาดเล็กสำหรับสตริงที่เป็นไปได้จำนวนมากแทนที่จะรวบรวมรายการความเป็นไปได้ตามตัวอักษรจำนวนมาก

ทั้งนี้ขึ้นอยู่กับหน่วยประมวลผล regex มีประมาณสิบสี่ metacharacters ตัวละครที่อาจจะหรืออาจจะไม่ได้ของพวกเขาที่แท้จริงความหมายตัวอักษรขึ้นอยู่กับบริบทหรือไม่ว่าพวกเขาจะ "หนี" คือนำหน้าด้วยลำดับหนี\ในกรณีนี้เครื่องหมาย regexes สมัยใหม่และ POSIX ใช้อักขระเมตาบ่อยกว่าความหมายตามตัวอักษรดังนั้นเพื่อหลีกเลี่ยง "backslash-osis" หรือโรคไม้จิ้มฟันเอนจึงเป็นเรื่องที่สมเหตุสมผลที่จะต้องหลีกหนี metacharacter ไปยังโหมดตามตัวอักษร แต่เริ่มต้นจากนั้นมันสมเหตุสมผลกว่าที่จะมีอักขระสี่ตัวคร่อมสี่ตัว( )และ{ }เป็นตัวอักษรเป็นหลักและ "หลบหนี" ความหมายปกตินี้ให้กลายเป็นอักขระเมตาคาแร็กเตอร์ มาตรฐานทั่วไปใช้ทั้งสองอย่าง metacharacters ปกติและ {}[]()^$.|*+? \ตัวละครปกติที่กลายเป็น metacharacters เมื่อหนีอยู่และdswDSWN

ตัวคั่น

เมื่อป้อน regex ในภาษาโปรแกรมอาจแสดงเป็นสตริงตามตัวอักษรตามปกติดังนั้นจึงมักจะยกมา นี้เป็นเรื่องธรรมดาใน C, Java และงูหลามตัวอย่างเช่นที่ regex ไม่ถูกป้อนเป็นre "re"อย่างไรก็ตามมักเขียนด้วยเครื่องหมายทับเป็นตัวคั่นเช่นเดียว/re/กับนิพจน์reทั่วไป สิ่งนี้เกิดขึ้นในedโดยที่/คำสั่งเอดิเตอร์สำหรับการค้นหาและ/re/สามารถใช้นิพจน์เพื่อระบุช่วงของบรรทัด (ตรงกับรูปแบบ) ซึ่งสามารถใช้ร่วมกับคำสั่งอื่น ๆ ในด้านใดด้านหนึ่งซึ่งมีชื่อเสียงมากที่สุดg/re/pเช่นเดียวกับในgrep ("global regex print ") ซึ่งรวมอยู่ในระบบปฏิบัติการที่ใช้Unixส่วนใหญ่เช่นลีนุกซ์ดิสทริบิวชัน สนธิสัญญาที่คล้ายกันคือใช้ในsedที่ค้นหาและแทนที่จะได้รับโดยรูปแบบและสามารถเข้าร่วมด้วยเครื่องหมายจุลภาคเพื่อระบุช่วงของสายในขณะที่s/re/replacement/ /re1/,/re2/สัญกรณ์นี้เป็นที่รู้จักกันดีโดยเฉพาะเนื่องจากใช้ในPerlซึ่งเป็นส่วนหนึ่งของไวยากรณ์ที่แตกต่างจากตัวอักษรสตริงปกติ ในบางกรณีเช่น sed และ Perl สามารถใช้ตัวคั่นทางเลือกเพื่อหลีกเลี่ยงการชนกับเนื้อหาและเพื่อหลีกเลี่ยงการหลีกเลี่ยงการเกิดขึ้นของอักขระตัวคั่นในเนื้อหา ตัวอย่างเช่นใน sed คำสั่งs,/,X,จะแทนที่ a /ด้วยXโดยใช้เครื่องหมายจุลภาคเป็นตัวคั่น

มาตรฐาน

IEEE POSIXมาตรฐานมีสามชุดของการปฏิบัติตาม: BRE (นิพจน์พื้นฐานปกติ) ^[29] ERE (ขยายนิพจน์ปกติ) และSRE (นิพจน์ปกติเรียบง่าย) SRE จะเลิก , ^[30]ในความโปรดปรานของ BRE ขณะที่ทั้งสองให้เข้ากันได้ย้อนหลัง ส่วนย่อยด้านล่างที่ครอบคลุมคลาสอักขระใช้กับทั้ง BRE และ ERE

BRE และ ERE ทำงานร่วมกัน ERE เพิ่ม?, +และ|และมันไม่จำเป็นต้องที่จะหลบหนี metacharacters ( )และ{ }ซึ่งจะต้องอยู่ใน BRE นอกจากนี้ตราบใดที่มีการปฏิบัติตามไวยากรณ์มาตรฐาน POSIX สำหรับ regexes อาจมีและมักจะเป็นไวยากรณ์เพิ่มเติมเพื่อรองรับแอปพลิเคชันที่เฉพาะเจาะจง (แต่เป็นไปตามมาตรฐาน POSIX) แม้ว่า POSIX.2 จะไม่ได้กำหนดเฉพาะการใช้งานบางส่วน แต่ BRE และ ERE ก็มี "มาตรฐาน" ซึ่งนับตั้งแต่นั้นมาได้ถูกนำมาใช้เป็นไวยากรณ์เริ่มต้นของเครื่องมือต่างๆโดยที่ตัวเลือกโหมด BRE หรือ ERE มักเป็นตัวเลือกที่รองรับ ตัวอย่างเช่นGNU grepมีตัวเลือกต่อไปนี้: " grep -E" สำหรับ ERE และ " grep -G" สำหรับ BRE (ค่าเริ่มต้น) และ " grep -P" สำหรับPerl regexes

Perl regexes ได้กลายเป็นมาตรฐานโดยพฤตินัยโดยมีชุดนิพจน์อะตอมที่หลากหลายและทรงพลัง Perl ไม่มีระดับ "พื้นฐาน" หรือ "ขยาย" เช่นเดียวกับใน POSIX EREs ( )และ{ }ถือว่าเป็นอักขระเมตาคาแร็กเตอร์เว้นแต่จะหลบหนี metacharacters อื่น ๆ เป็นที่รู้กันว่าเป็นตัวอักษรหรือสัญลักษณ์ตามบริบทเพียงอย่างเดียว ฟังก์ชันการทำงานเพิ่มเติมรวมถึงการจับคู่ขี้เกียจ , backreferencesชื่อกลุ่มการจับภาพและrecursiveรูปแบบ

POSIX พื้นฐานและแบบขยาย

ในPOSIXมาตรฐานพื้นฐานปกติไวยากรณ์ ( BRE ) กำหนดว่าmetacharacters ( )และ{ }จะกำหนด\(\)และ\{\}ในขณะที่การขยายปกติไวยากรณ์ ( ERE ) ไม่ได้

ตัวอย่าง:

• .at จับคู่สตริงอักขระสามตัวที่ลงท้ายด้วย "at" รวมถึง "hat" "cat" และ "bat"
• [hc]at จับคู่ "หมวก" และ "แมว"
• [^b]atจับคู่สตริงทั้งหมดที่จับคู่โดย.atยกเว้น "ค้างคาว"
• [^hc]atจับคู่สตริงทั้งหมดที่จับคู่โดย.atอื่นที่ไม่ใช่ "หมวก" และ "แมว"
• ^[hc]at จับคู่ "หมวก" และ "แมว" แต่จะอยู่ที่จุดเริ่มต้นของสตริงหรือบรรทัดเท่านั้น
• [hc]at$ จับคู่ "หมวก" และ "แมว" แต่จะอยู่ที่ส่วนท้ายของสตริงหรือบรรทัดเท่านั้น
• \[.\] จับคู่อักขระเดี่ยวใด ๆ ที่ล้อมรอบด้วย "[" และ "]" เนื่องจากวงเล็บจะเป็น Escape ตัวอย่างเช่น "[a]" และ "[b]"
• s.* จับคู่ตามด้วยอักขระศูนย์ขึ้นไปตัวอย่างเช่น "s" และ "saw" และ "seed"

POSIX ขยาย

ความหมายของอักขระที่หลีกเลี่ยงด้วยแบ็กสแลชจะกลับรายการสำหรับอักขระบางตัวในไวยากรณ์POSIX Extended Regular Expression ( ERE ) ด้วยไวยากรณ์นี้แบ็กสแลชจะทำให้ metacharacter ได้รับการปฏิบัติเป็นอักขระตามตัวอักษร ดังนั้นสำหรับตัวอย่างเช่น\( \)อยู่ในขณะนี้( )และอยู่ในขณะนี้\{ \} { }นอกจากนี้การสนับสนุนจะถูกลบออกสำหรับการอ้างอิงย้อนกลับและเพิ่มอักขระเมตาต่อไปนี้:\n

ตัวอย่าง:

• [hc]?at จับคู่ "at" "hat" และ "cat"
• [hc]*at จับคู่ "at", "hat", "cat", "hhat", "chat", "hcat", "cchchat" และอื่น ๆ
• [hc]+at จับคู่ "hat", "cat", "hhat", "chat", "hcat", "cchchat" และอื่น ๆ แต่ไม่ใช่ "at"
• cat|dog จับคู่ "แมว" หรือ "สุนัข"

POSIX ขยายนิพจน์ปกติมักจะสามารถใช้กับสาธารณูปโภค Unix ที่ทันสมัยโดยรวมบรรทัดคำสั่งธง-E

คลาสตัวละคร

คลาสอักขระเป็นแนวคิด regex พื้นฐานที่สุดหลังจากการจับคู่ตามตัวอักษร ทำให้ลำดับอักขระเล็ก ๆ หนึ่งตัวตรงกับชุดอักขระที่ใหญ่กว่า ตัวอย่างเช่นสามารถแทนตัวอักษรตัวพิมพ์ใหญ่ในตัวอักษรภาษาอังกฤษและอาจหมายถึงตัวเลขใดก็ได้ คลาสตัวละครนำไปใช้กับทั้งระดับ POSIX[A-Z]\d

เมื่อระบุช่วงของอักขระเช่น(เช่นตัวพิมพ์เล็กไปจนถึงตัวพิมพ์ใหญ่) การตั้งค่าโลแคลของคอมพิวเตอร์จะกำหนดเนื้อหาตามลำดับตัวเลขของการเข้ารหัสอักขระ พวกเขาสามารถเก็บตัวเลขในลำดับนั้นหรือสั่งซื้อสินค้าอาจจะabc ... zABC ... ZหรือaAbBcC ... ZZ ดังนั้นมาตรฐาน POSIX จึงกำหนดคลาสอักขระซึ่งจะทราบโดยตัวประมวลผล regex ที่ติดตั้ง คำจำกัดความเหล่านั้นอยู่ในตารางต่อไปนี้:[a-Z]aZ

คลาสอักขระ POSIX สามารถใช้ได้ภายในนิพจน์วงเล็บเท่านั้น ตัวอย่างเช่นจับคู่ตัวอักษรตัวพิมพ์ใหญ่และตัวพิมพ์เล็ก "a" และ "b"[[:upper:]ab]

คลาสที่ไม่ใช่ POSIX เพิ่มเติมที่เครื่องมือบางอย่างเข้าใจคือซึ่งโดยปกติจะกำหนดเป็นเครื่องหมายบวกขีดล่าง สิ่งนี้สะท้อนให้เห็นถึงความจริงที่ว่าในภาษาโปรแกรมหลายภาษาเหล่านี้เป็นอักขระที่อาจใช้ในตัวระบุ ตัวแก้ไขVimแยกความแตกต่างของคลาสwordและword-head เพิ่มเติม (โดยใช้สัญกรณ์และ) เนื่องจากในภาษาการเขียนโปรแกรมจำนวนมากอักขระที่สามารถเริ่มตัวระบุจะไม่เหมือนกับที่สามารถเกิดขึ้นในตำแหน่งอื่น ๆ : โดยทั่วไปตัวเลขจะถูกยกเว้นดังนั้นตัวระบุ จะมีลักษณะเหมือนหรือในสัญกรณ์ POSIX[:word:][:alnum:]\w\h\h\w*[[:alpha:]_][[:alnum:]_]*

โปรดสังเกตว่าสิ่งที่คลาสอักขระเรียกมาตรฐาน regex ของ POSIX มักเรียกว่าคลาสอักขระ POSIXในรสชาติ regex อื่น ๆ ที่รองรับ กับส่วนใหญ่รสชาติ regex อื่น ๆ ในระยะตัวละครคลาสถูกนำมาใช้เพื่ออธิบายสิ่งที่เรียก POSIX แสดงออกวงเล็บ

Perl และ PCRE

เนื่องจากความสามารถในการแสดงออกและความสะดวกในการอ่าน (สัมพัทธ์) ยูทิลิตี้และภาษาโปรแกรมอื่น ๆ จึงนำไวยากรณ์ที่คล้ายกับPerl มาใช้เช่นJava , JavaScript , Julia , Python , Ruby , Qt , .NET Frameworkของ Microsoft และXML สคีมา ภาษาและเครื่องมือบางอย่างเช่นBoostและPHPรองรับ regex หลายรสชาติ การใช้งาน regex Perl-derivative จะไม่เหมือนกันและโดยปกติจะใช้คุณลักษณะย่อยที่พบใน Perl 5.0 ซึ่งเผยแพร่ในปี 1994 บางครั้ง Perl จะรวมคุณลักษณะที่พบในภาษาอื่น ๆ ตัวอย่างเช่น Perl 5.10 ใช้ส่วนขยายทางวากยสัมพันธ์ที่พัฒนาขึ้นใน PCRE และ Python ^[32]

ขี้เกียจจับคู่

ในหลามและบางส่วนการใช้งานอื่น ๆ (เช่น Java) สามปริมาณที่พบบ่อย ( *, +และ?) มีความโลภโดยค่าเริ่มต้นเพราะพวกเขาตรงกับตัวละครมากที่สุดเท่าที่เป็นไปได้ ^[33]นิพจน์ทั่วไป".+"(รวมถึงเครื่องหมายอัญประกาศคู่) ที่ใช้กับสตริง

"แกนีมีด" เขากล่าวต่อ "เป็นดวงจันทร์ที่ใหญ่ที่สุดในระบบสุริยะ"

ตรงกับสายทั้งหมด (เพราะทั้งเส้นเริ่มต้นและจบลงด้วยการอ้างดับเบิล) "Ganymede,"แทนของการจับคู่เท่านั้นส่วนแรก ปริมาณดังกล่าวอาจอย่างไรจะทำขี้เกียจหรือน้อยที่สุดหรือไม่เต็มใจที่จับคู่เป็นตัวอักษรไม่กี่ที่เป็นไปได้โดยการผนวกเครื่องหมายคำถาม: ตรงเท่านั้น".+?" ^[33]"Ganymede,"

อย่างไรก็ตามประโยคทั้งหมดยังสามารถจับคู่ได้ในบางสถานการณ์ ตัวดำเนินการเครื่องหมายคำถามจะไม่เปลี่ยนความหมายของตัวดำเนินการจุดดังนั้นจึงยังสามารถจับคู่อัญประกาศคู่ในอินพุตได้ รูปแบบเช่น".*?" EOFจะยังคงตรงกับอินพุตทั้งหมดหากนี่คือสตริง:

"แกนีมีด" เขากล่าวต่อ "เป็นดวงจันทร์ที่ใหญ่ที่สุดในระบบสุริยะ" EOF

เพื่อให้แน่ใจว่าเครื่องหมายคำพูดคู่ไม่สามารถเป็นส่วนหนึ่งของการจับคู่ได้ต้องเปลี่ยนจุด (เช่น"[^"]*") สิ่งนี้จะจับคู่ส่วนข้อความที่ยกมาโดยไม่มีเครื่องหมายอัญประกาศคู่เพิ่มเติม (โดยการลบความเป็นไปได้ในการจับคู่คำต่อท้ายคงที่กล่าวคือ"สิ่งนี้ได้เปลี่ยนการจับคู่แบบขี้เกียจเป็นการจับคู่แบบโลภดังนั้นจึง?ไม่จำเป็นต้องใช้อีกต่อไป) ^{[ ต้องการอ้างอิง ]}

การจับคู่ที่เป็นไปได้

ใน Java ตัวระบุปริมาณอาจถูกทำให้เป็นเจ้าของได้โดยการต่อท้ายเครื่องหมายบวกซึ่งจะปิดใช้งานการสำรองข้อมูล (ในเอนจินการย้อนรอย) แม้ว่าการทำเช่นนั้นจะทำให้การจับคู่โดยรวมประสบความสำเร็จ: ^[34]ในขณะที่ regex ".*"นำไปใช้กับสตริง

"แกนีมีด" เขากล่าวต่อ "เป็นดวงจันทร์ที่ใหญ่ที่สุดในระบบสุริยะ"

ตรงกับสายทั้งหมด, regex ไม่".*+"ไม่ไม่ตรงกับที่ทุกคนเพราะกินการป้อนข้อมูลรวมทั้งในขั้นตอนสุดท้าย.*+ "ดังนั้นตัวระบุจำนวนที่เป็นเจ้าของจึงมีประโยชน์มากที่สุดกับคลาสอักขระที่ถูกลบเช่น"[^"]*+"ซึ่งจะจับคู่"Ganymede,"เมื่อนำไปใช้กับสตริงเดียวกัน

อีกส่วนขยายทั่วไปที่ให้บริการฟังก์ชันเดียวกันคือการจัดกลุ่มอะตอมซึ่งปิดใช้งานการย้อนกลับสำหรับกลุ่มในวงเล็บ ไวยากรณ์ทั่วไปคือ(?> กลุ่ม) ตัวอย่างเช่น while ^ (wi | w) i $ตรงกันทั้งคู่ wiและ wii , ^ (?> wi | w) i $เท่านั้นที่ตรงกัน wiiเนื่องจากเครื่องยนต์ถูกห้ามไม่ให้ย้อนรอยและลองตั้งค่ากลุ่มเป็น "w" ^[35]

ตัวระบุปริมาณที่เป็นไปได้นั้นง่ายต่อการใช้งานมากกว่าตัวระบุปริมาณที่โลภและขี้เกียจและโดยปกติแล้วจะมีประสิทธิภาพมากกว่าในรันไทม์ ^[34]

คุณสมบัติมากมายที่พบในไลบรารีนิพจน์ทั่วไปสมัยใหม่แทบทั้งหมดให้พลังในการแสดงออกที่เหนือกว่าภาษาทั่วไป ตัวอย่างเช่นการใช้งานจำนวนมากอนุญาตให้จัดกลุ่มนิพจน์ย่อยด้วยวงเล็บและเรียกคืนค่าที่ตรงกันในนิพจน์เดียวกัน (การอ้างอิงกลับ ) ซึ่งหมายความว่ารูปแบบสามารถจับคู่สตริงของคำซ้ำ ๆ เช่น "papa" หรือ "WikiWiki" ที่เรียกว่าสี่เหลี่ยมในทฤษฎีภาษาทางการ (.+)\1รูปแบบสำหรับสตริงเหล่านี้คือ

ภาษาของสี่เหลี่ยมไม่ปกติและไม่เป็นมันบริบทฟรีเนื่องจากการแทรกสูบน้ำ อย่างไรก็ตามการจับคู่แบบที่มีจำนวนมากมายของ backreferences เช่นการสนับสนุนโดยเครื่องมือที่ทันสมัยจำนวนมากยังคงเป็นบริบทที่สำคัญ ^[36]ปัญหาทั่วไปของการจับคู่การอ้างอิงย้อนกลับจำนวนเท่าใดก็ได้คือNP-completeซึ่งเพิ่มขึ้นอย่างทวีคูณตามจำนวนกลุ่มแบ็คอ้างอิงที่ใช้ ^[37]

อย่างไรก็ตามเครื่องมือไลบรารีและเอ็นจิ้นจำนวนมากที่ให้การสร้างดังกล่าวยังคงใช้คำว่านิพจน์ทั่วไปสำหรับรูปแบบของพวกเขา สิ่งนี้นำไปสู่ระบบการตั้งชื่อที่คำว่านิพจน์ทั่วไปมีความหมายแตกต่างกันในทฤษฎีภาษาที่เป็นทางการและการจับคู่รูปแบบ ด้วยเหตุนี้บางคนจึงใช้คำว่าregex , regexpหรือเพียงแค่รูปแบบเพื่ออธิบายความหลัง Larry Wallผู้เขียนภาษาโปรแกรม Perl เขียนในบทความเกี่ยวกับการออกแบบRaku :

"นิพจน์ทั่วไป" […] เกี่ยวข้องเพียงเล็กน้อยกับนิพจน์ทั่วไปจริง อย่างไรก็ตามคำนี้เติบโตขึ้นพร้อมกับความสามารถของเครื่องมือจับคู่รูปแบบของเราดังนั้นฉันจะไม่พยายามต่อสู้กับความจำเป็นทางภาษาที่นี่ อย่างไรก็ตามโดยทั่วไปฉันจะเรียกพวกเขาว่า "regexes" (หรือ "regexen" เมื่อฉันอยู่ในอารมณ์แองโกล - แซกซอน) ^[16]

คุณสมบัติอื่น ๆ ที่ไม่พบในการอธิบายภาษาทั่วไป ได้แก่ การยืนยัน ซึ่งรวมถึงที่แพร่หลาย ^และ $เช่นเดียวกับส่วนขยายที่ซับซ้อนมากขึ้นเช่น lookaround พวกเขากำหนดรอบของการจับคู่และไม่รั่วไหลในการจับคู่ซึ่งเป็นคุณลักษณะที่เกี่ยวข้องกับกรณีการใช้งานของการค้นหาสตริงเท่านั้น บางคนสามารถจำลองเป็นภาษาปกติได้โดยถือว่าสภาพแวดล้อมเป็นส่วนหนึ่งของภาษาเช่นกัน ^[38]

มีอัลกอริทึมที่แตกต่างกันอย่างน้อยสามรายการที่ตัดสินว่า regex ที่ระบุตรงกับสตริงหรือไม่และอย่างไร

สิ่งที่เก่าแก่ที่สุดและเร็วที่สุดนั้นอาศัยผลลัพธ์ในทฤษฎีภาษาที่เป็นทางการซึ่งอนุญาตให้ทุก ๆตัวที่ไม่ จำกัด ขอบเขตของออโตเมตัน (NFA) เปลี่ยนเป็นหุ่นยนต์ จำกัด (DFA) แบบกำหนดได้ DFA สามารถสร้างขึ้นอย่างชัดเจนจากนั้นรันบนสตริงอินพุตที่เป็นผลลัพธ์ทีละสัญลักษณ์ การสร้าง DFA สำหรับนิพจน์ทั่วไปของขนาดmมีเวลาและต้นทุนหน่วยความจำเท่ากับO (2 ^ม. ) แต่สามารถรันบนสตริงขนาดnในเวลาO ( n ) โปรดทราบว่าขนาดของนิพจน์เป็นขนาดหลังจากตัวย่อเช่นตัวระบุจำนวนตัวเลขได้ถูกขยาย

อีกทางเลือกหนึ่งคือการจำลอง NFA โดยตรงโดยสร้างสถานะ DFA ตามความต้องการเป็นหลักจากนั้นจึงทิ้งในขั้นตอนต่อไป สิ่งนี้ช่วยให้ DFA มีนัยสำคัญและหลีกเลี่ยงต้นทุนการก่อสร้างแบบเอ็กซ์โพเนนเชียล แต่ต้นทุนการดำเนินการเพิ่มขึ้นเป็นO ( mn ) วิธีการที่ชัดเจนเรียกว่าอัลกอริทึม DFA และวิธีการโดยนัยของอัลกอริทึม NFA การเพิ่มแคชลงในอัลกอริทึม NFA มักเรียกว่าอัลกอริทึม "lazy DFA" หรือเพียงแค่อัลกอริทึม DFA โดยไม่สร้างความแตกต่าง อัลกอริทึมเหล่านี้รวดเร็ว แต่การใช้เพื่อเรียกคืนนิพจน์ย่อยที่จัดกลุ่มการหาจำนวนที่ขี้เกียจและคุณลักษณะที่คล้ายกันนั้นยุ่งยาก ^{[39] [40]}การใช้งานสมัยใหม่รวมถึงตระกูล re1-re2-sregex ตามรหัสของ Cox

อัลกอริทึมที่สามคือการตรงกับรูปแบบกับสายป้อนโดยย้อนรอย อัลกอริทึมนี้เรียกโดยทั่วไปว่า NFA แต่คำศัพท์นี้อาจทำให้สับสนได้ เวลาในการทำงานอาจเป็นเลขชี้กำลังซึ่งการนำไปใช้งานอย่างง่ายจะแสดงเมื่อจับคู่กับนิพจน์เช่นนั้นมีทั้งการหาปริมาณแบบสลับและแบบไม่ถูกผูกมัดและบังคับให้อัลกอริทึมพิจารณาจำนวนกรณีย่อยที่เพิ่มขึ้นแบบทวีคูณ ลักษณะการทำงานนี้อาจทำให้เกิดปัญหาด้านความปลอดภัยที่เรียกว่าRegular expression Denial of Service (ReDoS)(a|aa)*b

แม้ว่าการใช้งานย้อนรอยจะให้การรับประกันแบบเอ็กซ์โพเนนเชียลในกรณีที่เลวร้ายที่สุด แต่ก็ให้ความยืดหยุ่นและพลังในการแสดงออกที่ดีกว่ามาก ตัวอย่างเช่นการนำไปใช้งานใด ๆ ที่อนุญาตให้ใช้การอ้างอิงย้อนกลับหรือใช้ส่วนขยายต่างๆที่ Perl นำมาใช้จะต้องมีการติดตามย้อนกลับบางประเภท การใช้งานบางอย่างพยายามให้อัลกอริทึมที่ดีที่สุดโดยการเรียกใช้อัลกอริทึม DFA ที่รวดเร็วก่อนและเปลี่ยนกลับไปใช้อัลกอริธึมการย้อนรอยที่อาจช้าลงก็ต่อเมื่อพบการอ้างอิงย้อนกลับในระหว่างการแข่งขัน GNU grep (และ gnulib DFA) ใช้กลยุทธ์ดังกล่าว ^[41]

อัลกอริธึมรันไทม์ Sublinear ทำได้โดยใช้อัลกอริทึมที่ใช้Boyer-Moore (BM)และเทคนิคการเพิ่มประสิทธิภาพ DFA ที่เกี่ยวข้องเช่นการสแกนย้อนกลับ ^[42] GNU grep ซึ่งรองรับไวยากรณ์และส่วนขยาย POSIX ที่หลากหลายใช้ BM สำหรับการกรองล่วงหน้าก่อนผ่านไปแล้วจึงใช้ DFA โดยนัย Wu agrepซึ่งใช้การจับคู่โดยประมาณรวมการกรองล่วงหน้าเข้ากับ DFA ใน BDM (การจับคู่ DAWG ย้อนหลัง) BNDM ของ NR-grep ขยายเทคนิค BDM ด้วย Shift-Or bit-level parallelism ^[43]

มีทางเลือกทางทฤษฎีสองสามทางในการย้อนกลับสำหรับการอ้างอิงย้อนกลับและ "เลขชี้กำลัง" ของพวกเขาเป็นตัวช่วยที่เกี่ยวข้องกับจำนวนการอ้างอิงย้อนกลับซึ่งเป็นคุณสมบัติคงที่ของภาษา regexp บางภาษาเช่น POSIX วิธีการไร้เดียงสาวิธีหนึ่งที่ทำซ้ำ NFA ที่ไม่ย้อนกลับสำหรับบันทึกการอ้างอิงแต่ละรายการมีความซับซ้อนของ${\ displaystyle {\ mathrm {O}} (n ^ {2k + 2})}$ เวลาและ ${\ displaystyle {\ mathrm {O}} (n ^ {2k + 1})}$ช่องว่างสำหรับกองหญ้าที่มีความยาว n และ k backreferences ใน RegExp ^[44]งานทางทฤษฎีล่าสุดที่ใช้หน่วยความจำออโตมาตาให้ขอบเขตที่แน่นขึ้นตามโหนดตัวแปร "แอ็คทีฟ" ที่ใช้และความเป็นไปได้ของพหุนามสำหรับ regexps ที่อ้างถึงย้อนกลับบางส่วน ^[45]

ในแง่ทฤษฎีชุดโทเค็นใด ๆ สามารถจับคู่โดยนิพจน์ทั่วไปได้ตราบเท่าที่มีการกำหนดไว้ล่วงหน้า ในแง่ของการใช้งานประวัติศาสตร์ regexes ถูกเขียนขึ้นมาเพื่อใช้ASCIIตัวอักษรเป็นชุดโทเค็นของพวกเขาแม้ว่าห้องสมุด regex ได้รับการสนับสนุนอื่น ๆ อีกมากมายชุดตัวอักษร หลายเครื่องยนต์ regex ทันสมัยมีอย่างน้อยการสนับสนุนบางส่วนสำหรับUnicode โดยส่วนใหญ่แล้วจะไม่แตกต่างกันว่าชุดอักขระคืออะไร แต่ปัญหาบางอย่างจะเกิดขึ้นเมื่อขยาย regexes เพื่อรองรับ Unicode

• การเข้ารหัสได้รับการสนับสนุน ไลบรารี regex บางแห่งคาดว่าจะทำงานกับการเข้ารหัสเฉพาะบางอย่างแทนที่จะใช้อักขระ Unicode ที่เป็นนามธรรม หลายเหล่านี้จำเป็นต้องใช้UTF-8เข้ารหัสขณะที่คนอื่นอาจคาดหวังUTF-16หรือUTF-32 ในทางตรงกันข้าม Perl และ Java ไม่เชื่อเรื่องพระเจ้าในการเข้ารหัสแทนที่จะดำเนินการกับอักขระที่ถอดรหัสภายใน
• ช่วงที่รองรับ Unicode เอ็นจิ้น regex จำนวนมากรองรับเฉพาะBasic Multilingual Planeนั่นคืออักขระที่เข้ารหัสได้เพียง 16 บิต ปัจจุบัน (ณ ปี 2559) มีเพียงเอนจิ้น regex เพียงไม่กี่ตัว (เช่น Perl และ Java) เท่านั้นที่สามารถรองรับช่วง Unicode แบบ 21 บิตเต็มรูปแบบได้
• ขยายโครงสร้าง ASCII ที่มุ่งเน้นการเป็น Unicode ตัวอย่างเช่นในการใช้งานแบบ ASCII ช่วงอักขระของแบบฟอร์ม[x-y]จะใช้ได้ทุกที่ที่xและyมีจุดรหัสอยู่ในช่วง [0x00,0x7F] และจุดรหัส ( x ) ≤ codepoint ( y ) ส่วนขยายตามธรรมชาติของช่วงอักขระดังกล่าวเป็น Unicode จะเปลี่ยนข้อกำหนดที่ให้ปลายทางอยู่ใน [0x00,0x7F] เป็นข้อกำหนดที่อยู่ใน [0x0000,0x10FFFF] อย่างไรก็ตามในทางปฏิบัติมักไม่เป็นเช่นนั้น การใช้งานบางอย่างเช่นgawkไม่อนุญาตให้ช่วงอักขระข้ามบล็อค Unicode ช่วงเช่น [0x61,0x7F] ถูกต้องเนื่องจากจุดสิ้นสุดทั้งสองอยู่ในบล็อกภาษาละตินพื้นฐานเช่นเดียวกับ [0x0530,0x0560] เนื่องจากจุดสิ้นสุดทั้งสองอยู่ในบล็อกอาร์เมเนีย แต่ช่วงเช่น [0x0061,0x0532] ไม่ถูกต้องเนื่องจากมี Unicode หลายบล็อก เอ็นจิ้นอื่น ๆ เช่นของตัวแก้ไขVimอนุญาตให้มีการข้ามบล็อก แต่ค่าอักขระต้องห่างกันไม่เกิน 256 ^[46]
• กรณีที่ไม่รู้สึก แฟล็กความไม่ไวต่อตัวพิมพ์เล็กและตัวพิมพ์มีผลเฉพาะอักขระ ASCII แฟล็กอื่นมีผลต่ออักขระทั้งหมด เอ็นจิ้นบางตัวมีแฟล็กที่แตกต่างกันสองแฟล็กหนึ่งสำหรับ ASCII และอีกอันสำหรับ Unicode อักขระที่อยู่ในคลาส POSIX ก็แตกต่างกันไปเช่นกัน
• ญาติของคดีไม่รู้สึก เนื่องจาก ASCII มีความแตกต่างของกรณีความไม่ไวต่อตัวพิมพ์จึงกลายเป็นคุณลักษณะเชิงตรรกะในการค้นหาข้อความ Unicode แนะนำสคริปต์ตัวอักษรโดยไม่ต้องกรณีเช่นเทวนาครี สำหรับสิ่งเหล่านี้ความไวของตัวพิมพ์เล็กและใหญ่ไม่สามารถใช้ได้ สำหรับสคริปต์เช่นภาษาจีนความแตกต่างอีกประการหนึ่งดูเหมือนจะเป็นเหตุเป็นผล: ระหว่างแบบดั้งเดิมและแบบเรียบง่าย ในสคริปต์ภาษาอาหรับอาจต้องการความไม่ไวต่อตำแหน่งเริ่มต้นตรงกลางขั้นสุดท้ายและตำแหน่งที่แยกได้ ในภาษาญี่ปุ่นความไม่รู้สึกไวระหว่างฮิรางานะและคาตาคานะบางครั้งก็มีประโยชน์
• นอร์มัลไลเซชัน Unicode ได้รวมตัวละคร เช่นเดียวกับเครื่องพิมพ์ดีดรุ่นเก่าตัวอักษรธรรมดาสามารถตามด้วยสัญลักษณ์ที่ไม่มีการเว้นวรรคหนึ่งตัวขึ้นไป (โดยปกติจะเป็นตัวกำกับเสียงเช่นเครื่องหมายเน้นเสียง) เพื่อสร้างอักขระการพิมพ์เดี่ยว แต่ยังมีอักขระที่มีการผสมไว้ล่วงหน้าเช่นอักขระที่มีอักขระรวมกันตั้งแต่หนึ่งตัวขึ้นไป ลำดับของอักขระ + อักขระที่รวมกันควรจับคู่กับอักขระนำหน้าเดี่ยวที่เหมือนกัน กระบวนการสร้างมาตรฐานของลำดับอักขระ + การรวมอักขระเรียกว่าการทำให้เป็นมาตรฐาน
• รหัสควบคุมใหม่ Unicode นำมาใช้ในหมู่คนอื่น ๆเครื่องหมายลำดับไบต์และเครื่องหมายบอกทิศทางข้อความ รหัสเหล่านี้อาจต้องได้รับการจัดการด้วยวิธีพิเศษ
• ความรู้เบื้องต้นของการเรียนตัวอักษรสำหรับบล็อก Unicode สคริปต์และหลายคุณสมบัติตัวอักษรอื่น คุณสมบัติบล็อกมีประโยชน์น้อยกว่าคุณสมบัติของสคริปต์เนื่องจากบล็อกสามารถมีจุดรหัสจากสคริปต์ที่แตกต่างกันหลาย ๆ สคริปต์และสคริปต์สามารถมีจุดรหัสจากบล็อกที่แตกต่างกันได้ ^[47]ในPerlและjava.util.regexไลบรารีคุณสมบัติของแบบฟอร์ม\p{InX}หรือ\p{Block=X}จับคู่อักขระในบล็อกXและ\P{InX}หรือ\P{Block=X}ตรงกับจุดรหัสที่ไม่อยู่ในบล็อกนั้น ในทำนองเดียวกัน\p{Armenian}, \p{IsArmenian}หรือ\p{Script=Armenian}ตรงกับตัวอักษรใด ๆ ในสคริปต์อาร์เมเนีย โดยทั่วไป\p{X}ตรงกับตัวอักษรใด ๆ กับทั้งคุณสมบัติไบนารีXหรือหมวดหมู่ทั่วไปX ตัวอย่างเช่น\p{Lu}, \p{Uppercase_Letter}หรือ\p{GC=Lu}ตรงกับอักษรตัวพิมพ์ใหญ่ใด ๆ คุณสมบัติไบนารีที่มีไม่ประเภททั่วไป ได้แก่\p{White_Space}, \p{Alphabetic}, และ\p{Math} \p{Dash}ตัวอย่างของคุณสมบัติที่ไม่ใช่ไบนารี\p{Bidi_Class=Right_to_Left}, และ\p{Word_Break=A_Letter}\p{Numeric_Value=10}

Regexes มีประโยชน์ในงานประมวลผลข้อความที่หลากหลายและโดยทั่วไปแล้วการประมวลผลสตริงโดยที่ข้อมูลไม่จำเป็นต้องเป็นข้อความ การใช้งานทั่วไปรวมถึงการตรวจสอบข้อมูล , ข้อมูลขูด (โดยเฉพาะเว็บขูด ), ข้อมูลการถกเถียงง่ายแยก , การผลิตของการเน้นไวยากรณ์ระบบและงานอื่น ๆ อีกมากมาย

แม้ว่า regexes จะมีประโยชน์ในเครื่องมือค้นหาทางอินเทอร์เน็ตแต่การประมวลผลทั่วทั้งฐานข้อมูลอาจใช้ทรัพยากรคอมพิวเตอร์มากเกินไปขึ้นอยู่กับความซับซ้อนและการออกแบบ regex แม้ว่าในหลาย ๆ กรณีผู้ดูแลระบบสามารถเรียกใช้การสืบค้นแบบ regex ภายในได้ แต่เครื่องมือค้นหาส่วนใหญ่ไม่ได้ให้การสนับสนุน regex แก่สาธารณะ ข้อยกเว้นเด่น ได้แก่การค้นหาของ Google รหัสและExalead อย่างไรก็ตาม Google Code Search ได้ปิดตัวลงในเดือนมกราคม 2555 ^[48]

กฎไวยากรณ์เฉพาะจะแตกต่างกันไปขึ้นอยู่กับการนำไปใช้งานภาษาโปรแกรมหรือไลบรารีที่ใช้งาน นอกจากนี้ฟังก์ชั่นการใช้งาน regex สามารถแตกต่างกันระหว่างรุ่น

เนื่องจากนิพจน์ทั่วไปอาจเป็นเรื่องยากที่จะอธิบายและทำความเข้าใจโดยไม่มีตัวอย่างเว็บไซต์เชิงโต้ตอบสำหรับการทดสอบนิพจน์ทั่วไปจึงเป็นแหล่งข้อมูลที่มีประโยชน์สำหรับการเรียนรู้นิพจน์ทั่วไปโดยการทดลอง ส่วนนี้ให้คำอธิบายพื้นฐานเกี่ยวกับคุณสมบัติบางประการของนิพจน์ทั่วไปโดยใช้ภาพประกอบ

ใช้อนุสัญญาต่อไปนี้ในตัวอย่าง ^[49]

metacharacter (s) ;; คอลัมน์ metacharacters ระบุไวยากรณ์ regex ที่กำลังแสดง= ~ ม // ;; บ่งชี้การดำเนินการจับคู่ regex ใน Perl= ~ s /// ;; บ่งชี้การดำเนินการแทนที่ regex ใน Perl

สิ่งที่น่าสังเกตก็คือ regexes เหล่านี้ล้วน แต่เป็นไวยากรณ์แบบ Perl นิพจน์ทั่วไปPOSIXมาตรฐานแตกต่างกัน

ตัวอย่างต่อไปนี้เป็นไปตามภาษาการเขียนโปรแกรมPerlรุ่น 5.8.8 31 มกราคม 2549 เว้นแต่จะระบุไว้เป็นอย่างอื่นซึ่งหมายความว่าการนำไปใช้งานอื่น ๆ อาจขาดการสนับสนุนบางส่วนของไวยากรณ์ที่แสดงไว้ที่นี่ (เช่นนิพจน์พื้นฐานเทียบกับนิพจน์ทั่วไป\( \)เทียบกับนิพจน์ทั่วไป()หรือขาด\dแทนPOSIX [:digit:] )

ไวยากรณ์และรูปแบบที่ใช้ในตัวอย่างเหล่านี้ตรงกับสภาพแวดล้อมการเขียนโปรแกรมอื่น ๆ เช่นกัน ^[50]

$ string1  =  "สวัสดีชาวโลก \ n" ; ถ้า ( $ string1  = ~  m /...../ )  {  พิมพ์ "$ string1 มีความยาว> = 5. \ n" ; }

สวัสดีชาวโลก มีความยาว> = 5

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / (H .. ). (o .. ) / )  {  พิมพ์ "เราจับคู่ '$ 1' และ '$ 2'. \ n" ; }

เราจับคู่ 'Hel' และ 'o W'

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / l + / )  {  พิมพ์ "มีตัวอักษรต่อเนื่อง \" l \ "อยู่ใน $ string1 อย่างน้อยหนึ่งตัว \ n" ; }

มีตัวอักษร "l" ติดกันอย่างน้อยหนึ่งตัวใน Hello World

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / H.? e / )  {  พิมพ์ "มี 'H' และ 'e' คั่นด้วย" ;  พิมพ์ "0-1 ตัวอักษร (เช่น He Hue Hee) \ n" ; }

มี 'H' และ 'e' คั่นด้วยอักขระ 0-1 (เช่น He Hue Hee)

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / (l. +? o) / )  {  พิมพ์ "การจับคู่แบบไม่โลภด้วย 'l' ตามด้วยหนึ่งหรือ" ;  พิมพ์ "อักขระเพิ่มเติมคือ" llo "แทนที่จะเป็น" llo Wo "\ n" ; }

การจับคู่แบบไม่โลภด้วย "l" ตามด้วยอักขระอย่างน้อยหนึ่งตัวคือ "llo" แทนที่จะเป็น "llo Wo"

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / el * o / )  {  พิมพ์ "มี 'e' ตามด้วยศูนย์ถึงหลาย" ;  พิมพ์ "'l' ตามด้วย 'o' (เช่น eo, elo, ello, elllo) \ n" ; }

มี 'e' ตามด้วยศูนย์ถึงหลาย 'l' ตามด้วย 'o' (เช่น eo, elo, ello, elllo)

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / l {1,2} / )  {  พิมพ์ "มีสตริงย่อยที่มีอย่างน้อย 1" ;  พิมพ์ "และมากที่สุด 2 l ใน $ string1 \ n" ; }

มีสตริงย่อยที่มีอย่างน้อย 1 และไม่เกิน 2 l ใน Hello World

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / [aeiou] + / )  {  พิมพ์ "$ string1 มีสระตั้งแต่หนึ่งตัวขึ้นไป \ n" ; }

สวัสดีชาวโลก มีสระอย่างน้อยหนึ่งเสียง

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / (สวัสดี | สวัสดี | Pogo) / )  {  พิมพ์ "$ string1 มี Hello, Hi หรือ Pogo อย่างน้อยหนึ่งรายการ" ; }

สวัสดีชาวโลก มีสวัสดีสวัสดีหรือ Pogo อย่างน้อยหนึ่งรายการ

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / llo \ b / )  {  พิมพ์ "มีคำที่ลงท้ายด้วย 'llo'. \ n" ; }

มีคำที่ลงท้ายด้วย 'llo'

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / \ w / )  {  พิมพ์ "มีตัวอักษรและตัวเลขอย่างน้อยหนึ่งตัว" ;  พิมพ์ "อักขระใน $ string1 (AZ, az, 0-9, _) \ n" ; }

มีอักขระที่เป็นตัวเลขและตัวอักษรอย่างน้อยหนึ่งตัวใน Hello World (AZ, az, 0-9, _)

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / \ W / )  {  พิมพ์ "ช่องว่างระหว่าง Hello และ" ;  พิมพ์ "โลกไม่ใช่ตัวเลขและตัวอักษร \ n" ; }

ช่องว่างระหว่าง Hello และ World ไม่ใช่ตัวเลขและตัวอักษร

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / \ s. * \ s / )  {  พิมพ์ "ใน $ string1 มีอักขระเว้นวรรคสองตัวซึ่งอาจ" ;  พิมพ์ "คั่นด้วยอักขระอื่น \ n" ; }

ใน Hello World มีอักขระช่องว่างสองอักขระซึ่งอาจคั่นด้วยอักขระอื่น

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / \ S. * \ S / )  {  พิมพ์ "ใน $ string1 มีอักขระที่ไม่ใช่ช่องว่าง 2 ตัวซึ่ง" ;  พิมพ์ "อาจคั่นด้วยอักขระอื่น \ n" ; }

ใน Hello World มีอักขระที่ไม่ใช่ช่องว่างสองอักขระซึ่งอาจคั่นด้วยอักขระอื่น ๆ

$ string1  =  "เบียร์ 99 ขวดบนผนัง" ; ถ้า ( $ string1  = ~  m / (\ d +) / )  {  พิมพ์ "$ 1 เป็นตัวเลขแรกใน '$ string1' \ n" ; }

99 เป็นหมายเลขแรกใน '99 ขวดเบียร์บนผนัง'

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / \ D / )  {  พิมพ์ "มีอักขระอย่างน้อยหนึ่งตัวใน $ string1" ;  พิมพ์ "ที่ไม่ใช่ตัวเลข \ n" ; }

มีอักขระอย่างน้อยหนึ่งตัวใน Hello World นั่นไม่ใช่ตัวเลข

$ string1  =  "สวัสดีชาวโลก \ n" ; if  ( $ string1  = ~  m / ^ He / )  {  พิมพ์ "$ string1 ขึ้นต้นด้วยอักขระ" He ". \ n" ; }

สวัสดีชาวโลก เริ่มต้นด้วยตัวละคร 'เขา'

$ string1  =  "สวัสดีชาวโลก \ n" ; ถ้า ( $ string1  = ~  m / rld $ / )  {  พิมพ์ "$ string1 เป็นบรรทัดหรือสตริง" ;  พิมพ์ "ที่ลงท้ายด้วย" rld ". \ n" ; }

สวัสดีชาวโลก คือบรรทัดหรือสตริงที่ลงท้ายด้วย 'rld'

$ string1  =  "สวัสดี \ nWorld \ n" ; ถ้า ( $ string1  = ~  m / \ AH / )  {  พิมพ์ "$ string1 เป็นสตริง" ;  พิมพ์ "ที่ขึ้นต้นด้วย" H "\ n" ; }

สวัสดีโลก คือสตริงที่ขึ้นต้นด้วย "H"

$ string1  =  "สวัสดี \ nWorld \ n" ; ถ้า ( $ string1  = ~  m / d \ n \ z / )  {  พิมพ์ "$ string1 เป็นสตริง" ;  พิมพ์ "ที่ลงท้ายด้วย 'd \\ n'. \ n" ; }

สวัสดีโลก คือสตริงที่ลงท้ายด้วย "d \ n"

$ string1  =  "สวัสดีชาวโลก \ n" ; ถ้า ( $ string1  = ~  m / [^ abc] / )  {  พิมพ์ "$ string1 มีอักขระอื่นที่ไม่ใช่" ;  พิมพ์ "a, b และ c. \ n" ; }

สวัสดีชาวโลก มีอักขระอื่นที่ไม่ใช่ a, b และ c

มักจะสร้างนิพจน์ทั่วไปได้ ("induced" หรือ "learn") ตามชุดสตริงตัวอย่าง นี้เป็นที่รู้จักในฐานะผู้ชักนำของภาษาปกติและเป็นส่วนหนึ่งของปัญหาทั่วไปของการเหนี่ยวนำไวยากรณ์ในทฤษฎีการเรียนรู้คอมพิวเตอร์ อย่างเป็นทางการยกตัวอย่างของสตริงในภาษาปกติและบางทียังให้ตัวอย่างของสตริงที่ไม่ได้อยู่ในภาษาปกตินั้นเป็นไปได้ที่จะทำให้เกิดไวยากรณ์สำหรับภาษากล่าวคือนิพจน์ทั่วไปที่สร้างภาษานั้น ภาษาปกติบางภาษาไม่สามารถเกิดขึ้นได้ด้วยวิธีนี้ (ดูการระบุภาษาในขีด จำกัด ) แต่สามารถทำได้หลายภาษา ตัวอย่างเช่นชุดของตัวอย่าง {1, 10, 100} และชุดค่าลบ (ของตัวอย่างตัวอย่าง) {11, 1001, 101, 0} สามารถใช้เพื่อชักนำให้เกิดนิพจน์ทั่วไป1⋅0 * (1 ตามด้วยศูนย์หรือมากกว่า 0 วินาที)

• การเปรียบเทียบเครื่องยนต์นิพจน์ทั่วไป
• แบบฟอร์ม Backus – Naur แบบขยาย
• การจับคู่อักขระตัวแทน
• ไวยากรณ์ของต้นไม้ปกติ
• โครงสร้างของทอมป์สัน - แปลงนิพจน์ทั่วไปให้เป็นหุ่นยนต์ จำกัด (NFA)

• สื่อที่เกี่ยวข้องกับRegexที่ Wikimedia Commons
• นิพจน์ทั่วไปที่Curlie
• ISO / IEC 9945-2: 1993 เทคโนโลยีสารสนเทศ - อินเทอร์เฟซระบบปฏิบัติการแบบพกพา (POSIX) - ส่วนที่ 2: เชลล์และยูทิลิตี้
• ISO / IEC 9945-2: 2002 เทคโนโลยีสารสนเทศ - อินเทอร์เฟซระบบปฏิบัติการแบบพกพา (POSIX) - ส่วนที่ 2: การเชื่อมต่อระบบ
• ISO / IEC 9945-2: 2003 เทคโนโลยีสารสนเทศ - อินเทอร์เฟซระบบปฏิบัติการแบบพกพา (POSIX) - ส่วนที่ 2: การเชื่อมต่อระบบ
• ISO / IEC / IEEE 9945: 2009 เทคโนโลยีสารสนเทศ - ข้อมูลจำเพาะพื้นฐานของระบบปฏิบัติการแบบพกพา (POSIX®) ฉบับที่ 7
• นิพจน์ทั่วไป, IEEE Std 1003.1-2017, Open Group