^(?=.{1,253}\.?$)(?:(?!-|[^.]+_)[A-Za-z0-9-_]{1,63}(?<!-)(?:\.|$)){2,}$
It is basically mkyong's answer and additionally:
Lookahead, limit max length between ^$ to 253 characters with optional trailing literal '.'
(?=.{1,253}\.?$)
Lookahead, next character is not a '-' and no '_' follows any characters before the next '.'. That is to say, enforce that the first character of a label isn't a '-' and only the first character may be a '_'.
(?!-|[^.]+_)
Between 1 and 63 of the allowed characters per label.
[A-Za-z0-9-_]{1,63}
Lookbehind, previous character not '-'. That is to say, enforce that the last character of a label isn't a '-'.
(?<!-)
Force a '.' at the end of every label except the last, where it is optional.
(?:\.|$)
Mostly combined from above, this requires at least two domain levels, which is not quite correct, but usually a reasonable assumption. Change from {2,} to + if you want to allow TLDs or unqualified relative subdomains through (eg, localhost, myrouter, to.)
(?:(?!-|[^.]+_)[A-Za-z0-9-_]{1,63}(?<!-)(?:\.|$)){2,}
Unit tests for this expression.